taskrambler  0.1.8
Web server and task management solution.
memory.c
Go to the documentation of this file.
1 /**
2  * \file This holds all stufff related our memory managent.
3  * I try the best as far as I can to reduce memory fragmentation
4  * and unneccessary calls to alloc and free.
5  *
6  * To achive this I try an approach described here as "Quick Fit".
7  * http://www.flounder.com/memory_allocation.htm
8  *
9  * The basic idea is to keep allocated memory segments and don't free
10  * them again. Instead I will put them in a tree indexed by their size.
11  * To get new memory I first have a look in the tree if there is
12  * a fitting memory segment. Fitting mean, larger or exactly the size
13  * I need. If there is one, use it. If not create a new one using
14  * usual malloc approach.
15  * I won't split the reagions at all because most likely they will be
16  * free soon again. This way I might waste some memory, so I have to
17  * keep an eye on this.
18  *
19  * Right now I don't build an upper limit for allocation. The limit
20  * still is the system memory itself.
21  *
22  * This is not implemented as a class because it will be used in the
23  * process of object creation.
24  *
25  * The data structure is a balanced tree with size as key.
26  * Under the size key is a list of elements of the same size.
27  *
28  * \author Georg Hopp
29  *
30  * \copyright
31  * Copyright © 2012 Georg Hopp
32  *
33  * This program is free software: you can redistribute it and/or modify
34  * it under the terms of the GNU General Public License as published by
35  * the Free Software Foundation, either version 3 of the License, or
36  * (at your option) any later version.
37  *
38  * This program is distributed in the hope that it will be useful,
39  * but WITHOUT ANY WARRANTY; without even the implied warranty of
40  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
41  * GNU General Public License for more details.
42  *
43  * You should have received a copy of the GNU General Public License
44  * along with this program. If not, see <http://www.gnu.org/licenses/>.
45  */
46 
47 #define _GNU_SOURCE
48 
49 #include <stdio.h>
50 
51 #include <stdlib.h>
52 #include <string.h>
53 #include <search.h>
54 #include <unistd.h>
55 
56 #include "utils/memory.h"
57 #include "tree.h"
58 
59 
60 struct memSegment
61 {
62  size_t ref_count;
63  size_t size;
64  void * ptr;
65 
66  enum rbColor color;
67 
68  struct memSegment * next;
69  struct memSegment * last;
70 
71  struct memSegment * parent;
72  struct memSegment * left;
73  struct memSegment * right;
74 };
75 
76 struct memSegment *
78 {
79  struct memSegment * element = malloc(size);
80 
81  element->ref_count = 1;
82  element->size = size;
83  element->ptr = (void*)element + sizeof(struct memSegment);
84 
85  element->next = NULL;
86  element->last = NULL;
87 
88  element->color = rbRed;
89  element->parent = NULL;
90  element->left = NULL;
91  element->right = NULL;
92 
93  return element;
94 }
95 
96 /**
97  * find element in tree
98  */
99 struct memSegment *
100 findElement(struct memSegment * tree, size_t size)
101 {
102  struct memSegment * fitting = NULL;
103 
104  while (NULL != tree) {
105  if (tree->size == size) {
106  fitting = tree;
107  break;
108  }
109 
110  if (size > tree->size) {
111  tree = tree->right;
112  } else {
113  fitting = tree;
114  tree = tree->left;
115  }
116  }
117 
118  return fitting;
119 }
120 
121 /*
122  * function to get specific elements needed for
123  * rb handling, grandparent, uncle and sibbling
124  */
125 struct memSegment *
126 grandparent(struct memSegment * node)
127 {
128  if (NULL != node && NULL != node->parent) {
129  return node->parent->parent;
130  }
131 
132  return NULL;
133 }
134 
135 struct memSegment *
136 uncle(struct memSegment * node)
137 {
138  struct memSegment * gp = grandparent(node);
139 
140  if (NULL == gp) {
141  return NULL;
142  }
143 
144  if (node->parent == gp->left) {
145  return gp->right;
146  }
147 
148  return gp->left;
149 }
150 
151 struct memSegment *
152 sibling(struct memSegment * node)
153 {
154  if (NULL == node) {
155  return NULL;
156  }
157 
158  if (NULL == node->parent->left || node == node->parent->left) {
159  return node->parent->right;
160  } else {
161  return node->parent->left;
162  }
163 }
164 
165 /*
166  * tree modifications...needed for rb handling.
167  */
168 void
169 rotateLeft(struct memSegment ** tree, struct memSegment * node)
170 {
171  struct memSegment * rightChild = node->right;
172  struct memSegment * rcLeftSub = node->right->left;
173 
174  rightChild->left = node;
175  rightChild->parent = node->parent;
176  node->right = rcLeftSub;
177  if (NULL != rcLeftSub) {
178  rcLeftSub->parent = node;
179  }
180 
181  if (node->parent) {
182  if (node->parent->left == node) {
183  node->parent->left = rightChild;
184  } else {
185  node->parent->right = rightChild;
186  }
187  } else {
188  *tree = rightChild;
189  }
190 
191  node->parent = rightChild;
192 }
193 
194 void
195 rotateRight(struct memSegment ** tree, struct memSegment * node)
196 {
197  struct memSegment * leftChild = node->left;
198  struct memSegment * lcRightSub = node->left->right;
199 
200  leftChild->right = node;
201  leftChild->parent = node->parent;
202  node->left = lcRightSub;
203  if (NULL != lcRightSub) {
204  lcRightSub->parent = node;
205  }
206 
207  if (node->parent) {
208  if (node->parent->left == node) {
209  node->parent->left = leftChild;
210  } else {
211  node->parent->right = leftChild;
212  }
213  } else {
214  *tree = leftChild;
215  }
216 
217  node->parent = leftChild;
218 }
219 
220 void
222  struct memSegment ** tree,
223  struct memSegment * node1,
224  struct memSegment * node2)
225 {
226  if (NULL != node1->parent) {
227  if (node1 == node1->parent->left) {
228  node1->parent->left = node2;
229  } else {
230  node1->parent->right = node2;
231  }
232  } else {
233  *tree = node2;
234  }
235 
236  if (NULL != node2) {
237  node2->parent = node1->parent;
238  }
239 }
240 
241 
242 /**
243  * insert element in tree
244  */
245 struct memSegment *
246 insertElement(struct memSegment ** tree, struct memSegment * element)
247 {
248  struct memSegment * node = *tree;
249  struct memSegment * new_node = NULL;
250  struct memSegment * u;
251  struct memSegment * g;
252 
253  element->next = NULL;
254  element->last = NULL;
255 
256  element->color = rbRed;
257  element->parent = NULL;
258  element->left = NULL;
259  element->right = NULL;
260 
261  // if tree is empty it's simple... :)
262  if (NULL == node) {
263  *tree = node = new_node = element;
264  } else {
265  // normal binary tree add....
266  while (NULL != node) {
267  if (element->size < node->size) {
268  if (NULL == node->left) {
269  node->left = element;
270  node->left->parent = node;
271  new_node = node = node->left;
272  break;
273  } else {
274  node = node->left;
275  }
276  } else if (element->size > node->size) {
277  if (NULL == node->right) {
278  node->right = element;
279  node->right->parent = node;
280  new_node = node = node->right;
281  break;
282  } else {
283  node = node->right;
284  }
285  } else {
286  if (NULL == node->next) {
287  node->next = element;
288  node->last = element;
289  } else {
290  node->last->next = element;
291  node->last = element;
292  }
293  return node;
294  }
295  }
296  }
297 
298  if (NULL != new_node) {
299  /*
300  * handle reballancing rb style
301  */
302  while (1) {
303  // case 1
304  if (node->parent == NULL) {
305  node->color = rbBlack;
306  // we're done.... :)
307  break;
308  }
309 
310  // case 2
311  if (node->parent->color == rbBlack) {
312  // Tree is still valid ... wow, again we're done... :)
313  break;
314  }
315 
316  // case 3
317  u = uncle(node);
318  g = grandparent(node);
319 
320  if (u != NULL && u->color == rbRed) {
321  node->parent->color = rbBlack;
322  u->color = rbBlack;
323  g->color = rbRed;
324 
325  node = g;
326  continue;
327  }
328 
329  // case 4
330  if (node == node->parent->right && node->parent == g->left) {
331  rotateLeft(tree, node->parent);
332  node = node->left;
333  } else if (node == node->parent->left && node->parent == g->right) {
334 
335  rotateRight(tree, node->parent);
336  node = node->right;
337  }
338 
339  // case 5
340  g = grandparent(node);
341 
342  node->parent->color = rbBlack;
343  g->color = rbRed;
344 
345  if (node == node->parent->left) {
346  rotateRight(tree, g);
347  } else {
348  rotateLeft(tree, g);
349  }
350 
351  // we're done..
352  break;
353  }
354  }
355 
356  return new_node;
357 }
358 
359 /**
360  * delete element from tree
361  * here multiple functions are involved....
362  * =======================================================================
363  */
364 /**
365  * find minimum of the right subtree aka leftmost leaf of right subtree
366  * aka left in-order successor.
367  * We return the parent of the element in the out argument parent.
368  * This can be NULL wenn calling.
369  *
370  * 2: *successor = {size = 80, ptr = 0x603ae0, color = rbRed, parent = 0x603160,
371  * left = 0x0, right = 0x0}
372  * 1: *node = {size = 70, ptr = 0x603a60, color = rbBlack, parent = 0x603070,
373  * left = 0x6030e0, right = 0x6031e0}
374  *
375  */
376 struct memSegment *
378 {
379  struct memSegment * node = tree->right;
380 
381  while (NULL != node->left) {
382  node = node->left;
383  }
384 
385  return node;
386 }
387 
388 struct memSegment *
389 deleteElement(struct memSegment ** tree, struct memSegment * element)
390 {
391  struct memSegment * node = *tree;
392  struct memSegment * del_node;
393  struct memSegment * child;
394  struct memSegment * s;
395 
396  // find the relevant node and it's parent
397  while (NULL != node) {
398 
399  if (element->size < node->size) {
400  node = node->left;
401  } else if (element->size > node->size) {
402  node = node->right;
403  } else {
404  if (NULL != node->next) {
405  if (NULL != node->parent) {
406  if (node == node->parent->left) {
407  node->parent->left = node->next;
408  } else {
409  node->parent->right = node->next;
410  }
411  } else {
412  *tree = node->next;
413  }
414 
415  if (NULL != node->left) {
416  node->left->parent = node->next;
417  }
418 
419  if (NULL != node->right) {
420  node->right->parent = node->next;
421  }
422 
423  node->next->last = node->last;
424  node->next->color = node->color;
425  node->next->parent = node->parent;
426  node->next->left = node->left;
427  node->next->right = node->right;
428 
429  return node;
430  }
431  break;
432  }
433  }
434 
435  // element not found
436  if (NULL == node) {
437  return node;
438  }
439 
440  del_node = node;
441 
442  // now our cases follows...the first one is the same as with
443  // simple binary search trees. Two non null children.
444 
445  // case 1: two children
446  if (NULL != node->left && NULL != node->right) {
447  struct memSegment * successor = findInOrderSuccessor(node);
448 
449  enum rbColor tmpcolor = successor->color;
450  struct memSegment * tmpparent = successor->parent;
451  struct memSegment * tmpleft = successor->left;
452  struct memSegment * tmpright = successor->right;
453 
454  replaceNode(tree, node, successor);
455 
456  successor->color = node->color;
457  successor->left = node->left;
458  successor->left->parent = successor;
459  // the right one might be successor...
460  if (node->right == successor) {
461  successor->right = node;
462  node->parent = successor;
463  } else {
464  successor->right = node->right;
465  node->right->parent = successor;
466  node->parent = tmpparent;
467  tmpparent->left = node;
468  }
469 
470  node->color = tmpcolor;
471  node->left = tmpleft;
472  node->right = tmpright;
473  }
474 
475  // Precondition: n has at most one non-null child.
476  child = (NULL == node->right) ? node->left : node->right;
477  replaceNode(tree, node, child);
478 
479  // delete one child case
480  // TODO this is overly complex as simply derived from the function...
481  // maybe this can be simplified. Maybe not...check.
482  if (node->color == rbBlack) {
483  if (NULL != child && child->color == rbRed) {
484  child->color = rbBlack;
485  // done despite modifying tree itself if neccessary..
486  return del_node;
487  } else {
488  if (NULL != child) {
489  node = child;
490  } else {
491  node->color = rbBlack;
492  node->left = NULL;
493  node->right = NULL;
494  }
495  }
496  } else {
497  return del_node;
498  }
499 
500  // delete and rb rebalance...
501  while(1) {
502  // case 1
503  if (NULL == node->parent) {
504  // done again
505  break;
506  }
507 
508  // case 2
509  s = sibling(node);
510 
511  if (NULL != s && s->color == rbRed) {
512  node->parent->color = rbRed;
513  s->color = rbBlack;
514 
515  /*
516  * detect which child we are...assumption
517  * if we are not parent->right and parent->right is not
518  * null we must be left, even if its set to NULL previously
519  */
520  if (NULL != node->parent->right && node != node->parent->right) {
521  rotateLeft(tree, node->parent);
522  } else {
523  rotateRight(tree, node->parent);
524  }
525  }
526 
527  s = sibling(node);
528  // case 3 / 4
529  if (NULL == s || ((s->color == rbBlack) &&
530  (NULL == s->left || s->left->color == rbBlack) &&
531  (NULL == s->right || s->right->color == rbBlack))) {
532 
533  if (NULL != s) {
534  s->color = rbRed;
535  }
536 
537  if (node->parent->color == rbBlack) {
538  // case 3
539  node = node->parent;
540  continue;
541  } else {
542  // case 4
543  node->parent->color = rbBlack;
544  // and done again...
545  break;
546  }
547  }
548 
549  // case 5
550  if (NULL != s && s->color == rbBlack) {
551  // this if statement is trivial,
552  // due to case 2 (even though case 2 changed the sibling to a
553  // sibling's child,
554  // the sibling's child can't be red, since no red parent can
555  // have a red child).
556  //
557  // the following statements just force the red to be on the
558  // left of the left of the parent,
559  // or right of the right, so case 6 will rotate correctly.
560  if ((node == node->parent->left) &&
561  (NULL == s->right || s->right->color == rbBlack) &&
562  (NULL != s->left && s->left->color == rbRed)) {
563 
564  // this last test is trivial too due to cases 2-4.
565  s->color = rbRed;
566  s->left->color = rbBlack;
567 
568  rotateRight(tree, s);
569  } else if ((node == node->parent->right) &&
570  (NULL == s->left || s->left->color == rbBlack) &&
571  (NULL != s->right && s->right->color == rbRed)) {
572  // this last test is trivial too due to cases 2-4.
573  s->color = rbRed;
574  s->right->color = rbBlack;
575 
576  rotateLeft(tree, s);
577  }
578  }
579 
580  s = sibling(node);
581  // case 6
582  if (NULL != s) {
583  s->color = node->parent->color;
584  }
585 
586  if (NULL != node && NULL != node->parent) {
587  node->parent->color = rbBlack;
588 
589  /*
590  * detect which child we are...assumption
591  * if we are not parent->right and parent->right is not
592  * null we must be left, even if its set to NULL previously
593  */
594  if (NULL != node->parent->right && node != node->parent->right) {
595  if (NULL != s->right) {
596  s->right->color = rbBlack;
597  }
598  rotateLeft(tree, node->parent);
599  } else {
600  if (NULL != s->left) {
601  s->left->color = rbBlack;
602  }
603  rotateRight(tree, node->parent);
604  }
605  }
606 
607  // done...
608  break;
609  }
610 
611  return del_node;
612 }
613 
614 
615 void
616 traverse(struct memSegment * tree, void (*cb)(struct memSegment *, int))
617 {
618  struct memSegment * previous = tree;
619  struct memSegment * node = tree;
620  int depth = 1;
621 
622  /*
623  * I think this has something like O(n+log(n)) on a ballanced
624  * tree because I have to traverse back the rightmost leaf to
625  * the root to get a break condition.
626  */
627  while (node) {
628  /*
629  * If we come from the right so nothing and go to our
630  * next parent.
631  */
632  if (previous == node->right) {
633  previous = node;
634  node = node->parent;
635  depth--;
636  continue;
637  }
638 
639  if ((NULL == node->left || previous == node->left)) {
640  /*
641  * If there are no more elements to the left or we
642  * came from the left, process data.
643  */
644  cb(node, depth);
645  previous = node;
646 
647  if (NULL != node->right) {
648  node = node->right;
649  depth++;
650  } else {
651  node = node->parent;
652  depth--;
653  }
654  } else {
655  /*
656  * if there are more elements to the left go there.
657  */
658  previous = node;
659  node = node->left;
660  depth++;
661  }
662  }
663 }
664 
665 void
666 post(struct memSegment * tree, void (*cb)(struct memSegment *, int))
667 {
668  struct memSegment * previous = tree;
669  struct memSegment * node = tree;
670  int depth = 1;
671 
672  /*
673  * I think this has something like O(n+log(n)) on a ballanced
674  * tree because I have to traverse back the rightmost leaf to
675  * the root to get a break condition.
676  */
677  while (node) {
678  /*
679  * If we come from the right so nothing and go to our
680  * next parent.
681  */
682  if (((NULL == node->left || previous == node->left)
683  && NULL == node->right)
684  || previous == node->right) {
685 
686  struct memSegment * parent = node->parent;
687 
688  cb(node, depth);
689 
690  previous = node;
691  node = parent;
692  depth--;
693  continue;
694  }
695 
696  if ((NULL == node->left || previous == node->left)) {
697  /*
698  * If there are no more elements to the left or we
699  * came from the left, process data.
700  */
701  previous = node;
702 
703  if (NULL != node->right) {
704  node = node->right;
705  depth++;
706  } else {
707  node = node->parent;
708  depth--;
709  }
710  } else {
711  /*
712  * if there are more elements to the left go there.
713  */
714  previous = node;
715  node = node->left;
716  depth++;
717  }
718  }
719 }
720 
721 void printElement(struct memSegment * node, int depth)
722 {
723  int i;
724 
725  printf("%s %010zu:%p(%02d)",
726  (node->color==rbRed)?"R":"B",
727  node->size,
728  node->ptr,
729  depth);
730  for (i=0; i<depth; i++) printf("-");
731  puts("");
732 
733  node = node->next;
734  while (NULL != node) {
735  printf(" %s %010zu:%p(%02d)",
736  (node->color==rbRed)?"R":"B",
737  node->size,
738  node->ptr,
739  depth);
740  for (i=0; i<depth; i++) printf("-");
741  puts("");
742  node = node->next;
743  }
744 }
745 
746 void
747 cleanup(struct memSegment * node, int depth)
748 {
749  while (NULL != node) {
750  struct memSegment * next = node->next;
751  free(node);
752  node = next;
753  }
754 }
755 
756 struct memSegment * segments = NULL;
757 
758 static
759 void
760 segmentFree(struct memSegment * segment, int depth)
761 {
762  while (NULL != segment) {
763  struct memSegment * next = segment->next;
764  free(segment);
765  segment = next;
766  }
767 }
768 
769 void *
770 memNewRef(void * mem)
771 {
772  struct memSegment * seg = (mem - sizeof(struct memSegment));
773 
774  seg->ref_count++;
775 
776  return mem;
777 }
778 
779 /*
780  * This will always allocate a multiple of PAGESIZE
781  */
782 void *
784 {
785  struct memSegment * seg = NULL;
786  //long psize = sysconf(_SC_PAGESIZE);
787  long psize = 64;
788 
789  size += sizeof(struct memSegment);
790 
791  /* allocate only blocks of a multiple of pagesize, similar to cbuf */
792  size = (0>=size)?1:(0!=size%psize)?(size/psize)+1:size/psize;
793  size *= psize;
794 
795 #ifdef MEM_OPT
796  seg = findElement(segments, size);
797 #endif
798 
799  if (NULL == seg) {
800  seg = newElement(size);
801  } else {
802  // remove the found one from the tree as we use it now.
803  seg = deleteElement(&segments, seg);
804  }
805 
806  return seg->ptr;
807 }
808 
809 /**
810  * this is a really memory wasting solution....just to be able to
811  * use calloc, which might be faster then malloc/memset solution.
812  *
813  * Maybe this is a bad idea, as we need to memset the buffer anyway
814  * if it comes from our tree, which hopefully should be the majority
815  * of cases.
816  */
817 void *
818 memCalloc(size_t nmemb, size_t size)
819 {
820  size_t _size = nmemb * size;
821  void * mem = memMalloc(_size);
822 
823  memset(mem, 0, _size);
824 
825  return mem;
826 }
827 
828 void
829 memFree(void ** mem)
830 {
831  if (NULL != *mem) {
832  struct memSegment * seg = (*mem - sizeof(struct memSegment));
833 
834  if (1 < seg->ref_count) {
835  seg->ref_count--;
836  } else {
837 #ifdef MEM_OPT
838  insertElement(&segments, seg);
839 #else
840  free(seg);
841 #endif
842  }
843 
844  *mem = NULL;
845  }
846 }
847 
848 size_t
849 memGetSize(void * mem)
850 {
851  struct memSegment * segment;
852 
853  if (NULL == mem) {
854  return 0;
855  }
856 
857  segment = (struct memSegment *)(mem - sizeof(struct memSegment));
858  return segment->size;
859 }
860 
861 void
863 {
864 #ifdef MEM_OPT
865  post(segments, segmentFree);
866 #endif
867 }
868 
869 // vim: set ts=4 sw=4:
void * memCalloc(size_t nmemb, size_t size)
Definition: memory.c:818
void memFree(void **mem)
Definition: memory.c:829
void * memMalloc(size_t size)
Definition: memory.c:783
struct memSegment * uncle(struct memSegment *node)
Definition: memory.c:136
struct memSegment * sibling(struct memSegment *node)
Definition: memory.c:152
struct memSegment * left
Definition: memory.c:72
struct memSegment * findInOrderSuccessor(struct memSegment *tree)
Definition: memory.c:377
void traverse(struct memSegment *tree, void(*cb)(struct memSegment *, int))
Definition: memory.c:616
static void(* cb)(const void *)
Definition: each.c:27
void replaceNode(struct memSegment **tree, struct memSegment *node1, struct memSegment *node2)
Definition: memory.c:221
void * ptr
Definition: memory.c:64
struct memSegment * last
Definition: memory.c:69
void * memNewRef(void *mem)
Definition: memory.c:770
void cleanup(struct memSegment *node, int depth)
Definition: memory.c:747
rbColor
Definition: tree.h:115
struct memSegment * deleteElement(struct memSegment **tree, struct memSegment *element)
Definition: memory.c:389
void rotateRight(struct memSegment **tree, struct memSegment *node)
Definition: memory.c:195
static size_t size
struct memSegment * newElement(size_t size)
Definition: memory.c:77
void memCleanup()
Definition: memory.c:862
struct memSegment * segments
Definition: memory.c:756
size_t size
Definition: memory.c:63
struct memSegment * parent
Definition: memory.c:71
size_t ref_count
Definition: memory.c:62
void printElement(struct memSegment *node, int depth)
Definition: memory.c:721
Definition: tree.h:115
size_t memGetSize(void *mem)
Definition: memory.c:849
enum rbColor color
Definition: memory.c:66
struct memSegment * next
Definition: memory.c:68
void rotateLeft(struct memSegment **tree, struct memSegment *node)
Definition: memory.c:169
void post(struct memSegment *tree, void(*cb)(struct memSegment *, int))
Definition: memory.c:666
struct memSegment * findElement(struct memSegment *tree, size_t size)
Definition: memory.c:100
static void segmentFree(struct memSegment *segment, int depth)
Definition: memory.c:760
struct memSegment * grandparent(struct memSegment *node)
Definition: memory.c:126
struct memSegment * right
Definition: memory.c:73
Definition: tree.h:115
struct memSegment * insertElement(struct memSegment **tree, struct memSegment *element)
Definition: memory.c:246