Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Mo Apr 12, 2021 03:41

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 17 Beiträge ]  Gehe zu Seite Vorherige  1, 2
Autor Nachricht
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Di Dez 30, 2014 22:30 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Ich hab ne bessere Idee ;)
[edit]
ich habe jetzt einen dummy hash eingebaut... die Leistung hat sich jetzt noch einmal verzehnfacht :)
Code:
  1.  
  2.  
  3.  
  4. //This is free and unencumbered software released into the public domain.
  5. //
  6. //Anyone is free to copy, modify, publish, use, compile, sell, or
  7. //distribute this software, either in source code form or as a compiled
  8. //binary, for any purpose, commercial or non - commercial, and by any
  9. //means.
  10. //
  11. //In jurisdictions that recognize copyright laws, the author or authors
  12. //of this software dedicate any and all copyright interest in the
  13. //software to the public domain.We make this dedication for the benefit
  14. //of the public at large and to the detriment of our heirs and
  15. //successors.We intend this dedication to be an overt act of
  16. //relinquishment in perpetuity of all present and future rights to this
  17. //software under copyright law.
  18. //
  19. //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  20. //EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  21. //MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  22. //IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  23. //OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  24. //ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  25. //OTHER DEALINGS IN THE SOFTWARE.
  26. //
  27. //For more information, please refer to <http://unlicense.org/>
  28.  
  29. #include "shared.h"
  30. //a simple linked list used by the garbage collector to build and
  31. //handle searches for references. Each reference found by the GC, will
  32. //be added to the list so we can search for children.
  33. struct memrng_t {
  34.     char * min;
  35.     char * max;
  36.     memrng_t * gcnext;
  37. };
  38.  
  39. struct memroot_t : memrng_t {
  40.     thread_id_t tid;
  41. };
  42.  
  43. //the following defines a ring-buffer for memory allocations. Each
  44. //node contains a lock so we can use it for "none-blocking" garbage
  45. //collection.
  46. struct memhdr_t : memrng_t {
  47.     size_t size; //includes header and fragments
  48.     bool mark;
  49.     bool isunused;
  50.     memhdr_t * next;
  51.     memhdr_t * skipprev;
  52.     memhdr_t * skipnext;
  53.     lock_t plock;
  54. };
  55.  
  56. static lock_t rlock = lock_t();
  57. static int num_roots = 0;
  58. static memroot_t *  roots = NULL;
  59. static memhdr_t * pool = NULL;
  60. static memhdr_t * pcur = NULL;
  61. static char * ps = NULL;
  62. static char * pe = NULL;
  63. static memhdr_t ** memcar = NULL;
  64.  
  65. int num_objects = 0;
  66. int num_deallocs = 0;
  67.  
  68.  
  69. void GCCollect(void) {
  70.     if (rlock.trylock()) {
  71.         memhdr_t * cur = pool;
  72.         memhdr_t * prev = NULL;
  73.         memhdr_t * fnd[NUM_SCAN_BUFFER + 1];
  74.         char * min[NUM_SCAN_BUFFER + 1];
  75.         char * max[NUM_SCAN_BUFFER + 1];
  76.         memrng_t * check = NULL;
  77.         char * ptr = NULL;
  78.         int mc = 0;
  79.         int tc = 0;
  80.         bool found = false;
  81.         size_t l = (pe - ps) / NUM_SCAN_BUFFER + 1;
  82.         size_t h = 0;
  83.         size_t g = 0;
  84.  
  85.         memset(max, 0, sizeof(max));
  86.         memset(min, 0xFFFFFF, sizeof(min));
  87.         memset(fnd, 0, sizeof(min));
  88.         //walk through each node and mark used nodes
  89.         //for garbage collection. Each node will be
  90.         //locked. It becomes unlocked when the next
  91.         //is locked or when the operation is completed.
  92.         do {
  93.             cur->plock.lock();
  94.             if (prev) {
  95.                 prev->plock.unlock();
  96.                 prev = NULL;
  97.             }
  98.             if (cur->isunused) {
  99.                 prev = cur;
  100.             } else {
  101.                 h = ((size_t)cur->min) / l;
  102.                 if (cur->min < min[h]) {
  103.                     min[h] = cur->min;
  104.                 }
  105.                 if (cur->max > max[h]) {
  106.                     max[h] = cur->max;
  107.                 }
  108.                 if (fnd[h]) {
  109.                     fnd[h]->skipprev = cur;
  110.                 }
  111.                 cur->skipnext = fnd[h];
  112.                 fnd[h] = cur;
  113.                 cur->mark = true;
  114.                 cur->isunused = true;
  115.                 ++mc;
  116.             }
  117.             cur = cur->next;
  118.         } while (cur != pool);
  119.         num_objects = mc;
  120.         if (prev) {
  121.             prev->plock.unlock();
  122.             prev = NULL;
  123.         }
  124.         //The following searches each node of a list for
  125.         //references to previously allocated memory. Each
  126.         //list item represents a range for memory from which
  127.         //each byte is searched for references to a block of
  128.         //memory.
  129.         for (int r = 0; r < num_roots; r++) {
  130.             roots[r].gcnext = check;
  131.             check = &(roots[r]);
  132.         }
  133.         tc = mc;
  134.         while (check && tc) {
  135.             char * c = check->min;
  136.             char * e = check->max;
  137.             while (c < e && tc) {
  138.                 ptr = *((char**)c++);
  139.  
  140.                 if (ptr) {
  141.                     h = ((size_t)ptr) / l;
  142.                     found = false;
  143.                     for (int i = h; i <= NUM_SCAN_BUFFER && !found; i++) {
  144.                         if (ptr >= min[h] && ptr <= max[h]) {
  145.                             g = (ps- ps) / sizeof(memhdr_t);
  146.                             cur = memcar[g];
  147.                             if (cur && cur->mark && cur->isunused) {
  148.                                 cur->isunused = false;
  149.                                 cur->mark = false;
  150.                                 --tc;
  151.                                 if (cur->skipprev) {
  152.                                     cur->skipprev->skipnext = cur->skipnext;
  153.                                 } else {
  154.                                     fnd[h] = cur->skipnext;
  155.                                 }
  156.                                 cur->gcnext = check->gcnext;
  157.                                 check->gcnext = cur;
  158.                                 cur->plock.unlock();
  159.                                 found = true;
  160.                                 c += sizeof(char*) - 1;
  161.                             }
  162.                         }
  163.                     }
  164.                 } else {
  165.                     c += sizeof(char*) - 1;
  166.                 }
  167.             }
  168.             if (check == check->gcnext) {
  169.                 system("pause");
  170.             }
  171.             check = check->gcnext;
  172.         }
  173.         //now walk through each remaining node and unlock them
  174.         //so they may get reused by GCAlloc.
  175.         num_objects -= mc - tc;
  176.         mc = 0;
  177.         for (int i = 0; i < NUM_SCAN_BUFFER; i++) {
  178.             while (fnd[i]) {
  179.                 prev = fnd[i];
  180.                 fnd[i] = fnd[i]->skipnext;
  181.                 prev->mark = false;
  182.                 prev->plock.unlock();
  183.                 mc++;
  184.             }
  185.         }
  186.         num_deallocs = mc;
  187.     } else {
  188.         rlock.lock(); //just wait when gc is in progress
  189.     }
  190.     rlock.unlock();
  191. }
  192.  
  193. void * GCAlloc(size_t size) {
  194.     if (size) {
  195.         bool firstry = true;
  196.         if (num_objects > NUM_OBJECT_SLOWDOWN) { //slow down allocator when dealing with many objects
  197.             Sleep(num_objects / NUM_OBJECT_SLOWDOWN * 10);
  198.         }
  199.         size += sizeof(memhdr_t); //add block header size
  200.         size += sizeof(char*);
  201.         size = (size + (sizeof(memhdr_t) - 1)) & ~(sizeof(memhdr_t) - 1); //align
  202.     secondtry:
  203.         //you might want to use pool instead of pcur
  204.         //when dealing with many small objects as it runs
  205.         //a bit smoother in this case.
  206.         memhdr_t * start = pcur;
  207.         memhdr_t * cur = start;
  208.         memhdr_t * prev = NULL;
  209.         do {
  210.             if (cur->plock.trylock()) {
  211.                 if (cur->isunused) {
  212.                     //merge coherent blocks
  213.                     while (cur < cur->next && cur->next->plock.trylock()) {
  214.                         if (cur->next->isunused) {
  215.                             cur->size += cur->next->size;
  216.                             cur->next = cur->next->next;
  217.                         } else {
  218.                             cur->next->plock.unlock();
  219.                             break;
  220.                         }
  221.                     }
  222.                     if (cur->size >= size) {
  223.                         size_t left = cur->size - size;
  224.                         //split the block if its big enough to hold another value
  225.                         if (left > (sizeof(memhdr_t) + 64)) {
  226.                             memhdr_t * split = (memhdr_t*)(((char*)cur) + size);
  227.                             split->size = left;
  228.                             split->isunused = true;
  229.                             split->next = cur->next;
  230.                             split->min = ((char*)split) + sizeof(memhdr_t);
  231.                             split->max = ((char*)split) + split->size - sizeof(char*);
  232.                             split->plock.unlock();
  233.                             cur->size = size;
  234.                             cur->max = ((char*)cur) + cur->size - sizeof(char*);
  235.                             cur->next = split;
  236.                             pcur = split;
  237.                         }
  238.                         left = cur->size / sizeof(memhdr_t);
  239.                         size_t y = (cur - pool) / sizeof(memhdr_t);
  240.                         left += y;
  241.                         for (size_t x = y; x < left; x++) {
  242.                             memcar[x] = cur;
  243.                         }
  244.                         cur->isunused = false;
  245.                         cur->mark = false;
  246.                         cur->plock.unlock();
  247.                         ++num_objects;
  248.                         return (void*)cur->min;
  249.                     }
  250.                 }
  251.                 prev = cur;
  252.                 cur = cur->next;
  253.                 prev->plock.unlock();
  254.             } else {
  255.                 cur = cur->next;
  256.             }
  257.         } while (cur != start);
  258.         if (firstry) {
  259.             firstry = false;
  260.             GCCollect();
  261.             goto secondtry;
  262.         }
  263.     }
  264.     return NULL;
  265. }
  266.  
  267.  
  268. void GCInit(void) {
  269.     pool = (memhdr_t*)calloc(MEMORY_POOL_SIZE + sizeof(memhdr_t) + 1, 1);
  270.     memcar = (memhdr_t**)calloc(MEMORY_POOL_SIZE / sizeof(memhdr_t), sizeof(memhdr_t*));
  271.  
  272.     if (pool && memcar) {
  273.         pool->size = MEMORY_POOL_SIZE;
  274.         pool->next = pool;
  275.         pool->isunused = true;
  276.         ps = pool->min = ((char*)pool) + sizeof(memhdr_t);
  277.         pe = pool->max = pool->min + MEMORY_POOL_SIZE - sizeof(char*);
  278.         pool->plock.unlock();
  279.     }
  280.     pcur = pool;
  281.     num_objects = 0;
  282. }
  283.  
  284. void GCShutdown(void) {
  285.     free(pool);
  286.     free(memcar);
  287.     pool = NULL;
  288.     memcar = NULL;
  289.     pcur = NULL;
  290.     ps = pe = NULL;
  291.     num_objects = 0;
  292. }
  293.  
  294. void GCRegisterRoot(thread_id_t id, char * min, char * max) {
  295.     rlock.lock();
  296.     for (int i = 0; i < num_roots; i++) {
  297.         if (memcmp(&(roots[i].tid), &id, sizeof(thread_id_t)) == 0) {
  298.             roots[i].min = min;
  299.             roots[i].max = max - sizeof(char*);
  300.             rlock.unlock();
  301.             return;
  302.         }
  303.     }
  304.     if (num_roots % 10 == 0) {
  305.         if (num_roots == 0) {
  306.             GCInit();
  307.         }
  308.         int nr = (num_roots / 10 + 1) * 10 + 1;
  309.         memroot_t * tmp = roots;
  310.         roots = (memroot_t*)calloc(nr, sizeof(memroot_t));
  311.         if (tmp) {
  312.             memcpy(roots, tmp, sizeof(memroot_t)*num_roots);
  313.             free(tmp);
  314.         }
  315.     }
  316.     roots[num_roots].min = min;
  317.     roots[num_roots].max = max - sizeof(char*);
  318.     memcpy(&(roots[num_roots].tid), &id, sizeof(thread_id_t));
  319.     roots[num_roots++].gcnext = NULL;
  320.     rlock.unlock();
  321. }
  322.  
  323. void GCUnregisterRoot(thread_id_t id) {
  324.     rlock.lock();
  325.     if (num_roots == 1) {
  326.         GCShutdown();
  327.         free(roots);
  328.         roots = NULL;
  329.     } else {
  330.         for (int i = 0; i < num_roots; i++) {
  331.             if (memcmp(&(roots[i].tid), &id, sizeof(thread_id_t))) {
  332.                 continue;
  333.             }
  334.             for (int j = i; j < num_roots; j++) {
  335.                 memcpy(&(roots[j]), &(roots[j + 1]), sizeof(memroot_t));
  336.             }
  337.             break;
  338.         }
  339.         num_roots--;
  340.     }
  341.     rlock.unlock();
  342. }
  343.  
  344. void GCFree(void * ptr) {
  345.     if (ptr) {
  346.         memhdr_t * hdr = (memhdr_t*)(((char*)ptr) - sizeof(memhdr_t));
  347.         if (rlock.trylock() && hdr->min == ptr && hdr->plock.trylock()) {
  348.             hdr->isunused = false;
  349.             rlock.unlock();
  350.             hdr->plock.unlock();
  351.         }
  352.     }
  353. }
  354.  
  355. void * operator new(size_t size){
  356.     return GCAlloc(size);
  357. }
  358.  
  359. void * operator new[](size_t size) {
  360.     return GCAlloc(size);
  361. }
  362.  
  363. void operator delete(void * ptr) {
  364.     GCFree(ptr);
  365. }
  366.  
  367. void operator delete[](void * ptr) {
  368.     GCFree(ptr);
  369. }
  370.  
  371.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Mini Collector
BeitragVerfasst: Mi Dez 31, 2014 16:29 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Diese Version ist sehr viel langsamer, dafür gibt es jetzt aber endlich den "worldstop". Dabei werden die Threads der registrierten Roots kurz während der Collection pausiert. Die Frage ist jetzt ob man das Suspend und Resume irgendwie umgehen könnte...

Code:
  1.  
  2.  
  3.  
  4. //This is free and unencumbered software released into the public domain.
  5. //
  6. //Anyone is free to copy, modify, publish, use, compile, sell, or
  7. //distribute this software, either in source code form or as a compiled
  8. //binary, for any purpose, commercial or non - commercial, and by any
  9. //means.
  10. //
  11. //In jurisdictions that recognize copyright laws, the author or authors
  12. //of this software dedicate any and all copyright interest in the
  13. //software to the public domain.We make this dedication for the benefit
  14. //of the public at large and to the detriment of our heirs and
  15. //successors.We intend this dedication to be an overt act of
  16. //relinquishment in perpetuity of all present and future rights to this
  17. //software under copyright law.
  18. //
  19. //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  20. //EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  21. //MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  22. //IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  23. //OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  24. //ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  25. //OTHER DEALINGS IN THE SOFTWARE.
  26. //
  27. //For more information, please refer to <http://unlicense.org/>
  28.  
  29. #include "shared.h"
  30. //a simple linked list used by the garbage collector to build and
  31. //handle searches for references. Each reference found by the GC, will
  32. //be added to the list so we can search for children.
  33. struct memrng_t {
  34.     char * min;
  35.     char * max;
  36.    
  37.     memrng_t * gcnext;
  38. };
  39.  
  40. struct memroot_t : memrng_t {
  41.     thread_id_t tid;
  42.     HANDLE thread;
  43. };
  44.  
  45. //the following defines a ring-buffer for memory allocations. Each
  46. //node contains a lock so we can use it for "none-blocking" garbage
  47. //collection.
  48. struct memhdr_t : memrng_t {
  49.     size_t size; //includes header and fragments
  50.     bool mark;
  51.     bool isunused;
  52.     memhdr_t * next;
  53.     memhdr_t * skipprev;
  54.     memhdr_t * skipnext;
  55.     lock_t plock;
  56. };
  57.  
  58. static lock_t rlock = lock_t();
  59. static int num_roots = 0;
  60. static memroot_t *  roots = NULL;
  61. static memhdr_t * pool = NULL;
  62. static memhdr_t * pcur = NULL;
  63. static char * ps = NULL;
  64. static char * pe = NULL;
  65. static memhdr_t ** memcar = NULL;
  66.  
  67. int num_objects = 0;
  68. int num_deallocs = 0;
  69.  
  70.  
  71. void GCCollect(void) {
  72.     if (rlock.trylock()) {
  73.         DWORD cid = GetCurrentThreadId();
  74.         memhdr_t * cur = pool;
  75.         memhdr_t * prev = NULL;
  76.         memhdr_t * fnd[NUM_SCAN_BUFFER + 1];
  77.         char * min[NUM_SCAN_BUFFER + 1];
  78.         char * max[NUM_SCAN_BUFFER + 1];
  79.         memrng_t * check = NULL;
  80.         memrng_t * fcheck = NULL;
  81.         char * ptr = NULL;
  82.         int mc = 0;
  83.         int tc = 0;
  84.         bool found = false;
  85.         size_t l = (pe - ps) / NUM_SCAN_BUFFER + 1;
  86.         size_t h = 0;
  87.         size_t g = 0;
  88.  
  89.         memset(max, 0, sizeof(max));
  90.         memset(min, 0xFFFFFF, sizeof(min));
  91.         memset(fnd, 0, sizeof(min));
  92.         //walk through each node and mark used nodes
  93.         //for garbage collection. Each node will be
  94.         //locked. It becomes unlocked when the next
  95.         //is locked or when the operation is completed.
  96.         do {
  97.             cur->plock.lock();
  98.             if (prev) {
  99.                 prev->plock.unlock();
  100.                 prev = NULL;
  101.             }
  102.             if (cur->isunused) {
  103.                 prev = cur;
  104.             } else {
  105.                 h = ((size_t)cur->min) / l;
  106.                 if (cur->min < min[h]) {
  107.                     min[h] = cur->min;
  108.                 }
  109.                 if (cur->max > max[h]) {
  110.                     max[h] = cur->max;
  111.                 }
  112.                 if (fnd[h]) {
  113.                     fnd[h]->skipprev = cur;
  114.                 }
  115.                 cur->skipnext = fnd[h];
  116.                 fnd[h] = cur;
  117.                 cur->mark = true;
  118.                 cur->isunused = true;
  119.                 ++mc;
  120.             }
  121.             cur = cur->next;
  122.         } while (cur != pool);
  123.         num_objects = mc;
  124.         if (prev) {
  125.             prev->plock.unlock();
  126.             prev = NULL;
  127.         }
  128.         tc = mc;
  129.         //The following searches each node of a list for
  130.         //references to previously allocated memory. Each
  131.         //list item represents a range for memory from which
  132.         //each byte is searched for references to a block of
  133.         //memory.
  134.         for (int r = 0; r < num_roots; r++) {
  135.             roots[r].gcnext = check;
  136.             check = &(roots[r]);
  137.         }
  138.         fcheck = check;
  139.         while (check && tc) {
  140.             char * c = check->min;
  141.             char * e = check->max;
  142.             while (c < e && tc) {
  143.                 ptr = *((char**)c++);
  144.  
  145.                 if (ptr) {
  146.                     h = ((size_t)ptr) / l;
  147.                     found = false;
  148.                     for (int i = h; i <= NUM_SCAN_BUFFER && !found; i++) {
  149.                         if (ptr >= min[h] && ptr <= max[h]) {
  150.                             g = (ps - ps) / sizeof(memhdr_t);
  151.                             cur = memcar[g];
  152.                             if (cur && cur->mark && cur->isunused) {
  153.                                 cur->isunused = false;
  154.                                 cur->mark = false;
  155.                                 --tc;
  156.                                 if (cur->skipprev) {
  157.                                     cur->skipprev->skipnext = cur->skipnext;
  158.                                 } else {
  159.                                     fnd[h] = cur->skipnext;
  160.                                 }
  161.                                 cur->gcnext = check->gcnext;
  162.                                 check->gcnext = cur;
  163.                                 cur->plock.unlock();
  164.                                 found = true;
  165.                                 c += sizeof(char*) - 1;
  166.                             }
  167.                         }
  168.                     }
  169.                 } else {
  170.                     c += sizeof(char*) - 1;
  171.                 }
  172.             }
  173.             if (check == check->gcnext) {
  174.                 system("pause");
  175.             }
  176.            
  177.             check = check->gcnext;
  178.         }
  179.         //run collection a second time but this time pause
  180.         //any registered thread so we can be that nothing is
  181.         //misssed
  182.         if (tc > 0) {
  183.             for (int r = 0; r < num_roots; r++) {
  184.                 if (cid != roots[r].tid.tid) {
  185.                     //pause threads so pointers can't be moved
  186.                     while (SuspendThread(roots[r].thread) == (DWORD)-1) {
  187.                         Sleep(20);
  188.                     }
  189.                 }
  190.             }
  191.             check = fcheck;
  192.             while (check && tc) {
  193.                 char * c = check->min;
  194.                 char * e = check->max;
  195.                 while (c < e && tc) {
  196.                     ptr = *((char**)c++);
  197.  
  198.                     if (ptr) {
  199.                         h = ((size_t)ptr) / l;
  200.                         found = false;
  201.                         for (int i = h; i <= NUM_SCAN_BUFFER && !found; i++) {
  202.                             if (ptr >= min[h] && ptr <= max[h]) {
  203.                                 g = (ps - ps) / sizeof(memhdr_t);
  204.                                 cur = memcar[g];
  205.                                 if (cur && cur->mark && cur->isunused) {
  206.                                     cur->isunused = false;
  207.                                     cur->mark = false;
  208.                                     --tc;
  209.                                     if (cur->skipprev) {
  210.                                         cur->skipprev->skipnext = cur->skipnext;
  211.                                     } else {
  212.                                         fnd[h] = cur->skipnext;
  213.                                     }
  214.                                     cur->gcnext = check->gcnext;
  215.                                     check->gcnext = cur;
  216.                                     cur->plock.unlock();
  217.                                     found = true;
  218.                                     c += sizeof(char*) - 1;
  219.                                 }
  220.                             }
  221.                         }
  222.                     } else {
  223.                         c += sizeof(char*) - 1;
  224.                     }
  225.                 }
  226.                 if (check == check->gcnext) {
  227.                     system("pause");
  228.                 }
  229.  
  230.                 check = check->gcnext;
  231.             }
  232.  
  233.             for (int r = 0; r < num_roots; r++) {
  234.                 if (cid != roots[r].tid.tid) {
  235.                     //resume threads
  236.                     while (ResumeThread(roots[r].thread) == (DWORD)-1) {
  237.                         Sleep(20);
  238.                     }
  239.                 }
  240.             }
  241.         }
  242.         //now walk through each remaining node and unlock them
  243.         //so they may get reused by GCAlloc.
  244.         num_objects -= mc - tc;
  245.         mc = 0;
  246.         for (int i = 0; i < NUM_SCAN_BUFFER; i++) {
  247.             while (fnd[i]) {
  248.                 prev = fnd[i];
  249.                 fnd[i] = fnd[i]->skipnext;
  250.                 prev->mark = false;
  251.                 prev->plock.unlock();
  252.                 mc++;
  253.             }
  254.         }
  255.         num_deallocs = mc;
  256.     } else {
  257.         rlock.lock(); //just wait when gc is in progress
  258.     }
  259.     rlock.unlock();
  260. }
  261.  
  262. void * GCAlloc(size_t size) {
  263.     if (size) {
  264.         bool firstry = true;
  265.         size += sizeof(memhdr_t); //add block header size
  266.         size += sizeof(char*);
  267.         size = (size + (sizeof(memhdr_t) - 1)) & ~(sizeof(memhdr_t) - 1); //align
  268.     secondtry:
  269.         //you might want to use pool instead of pcur
  270.         //when dealing with many small objects as it runs
  271.         //a bit smoother in this case.
  272.         memhdr_t * start = pcur;
  273.         memhdr_t * cur = start;
  274.         memhdr_t * prev = NULL;
  275.         do {
  276.             if (cur->plock.trylock()) {
  277.                 if (cur->isunused) {
  278.                     //merge coherent blocks
  279.                     while (cur < cur->next && cur->next->plock.trylock()) {
  280.                         if (cur->next->isunused) {
  281.                             cur->size += cur->next->size;
  282.                             cur->next = cur->next->next;
  283.                         } else {
  284.                             cur->next->plock.unlock();
  285.                             break;
  286.                         }
  287.                     }
  288.                     if (cur->size >= size) {
  289.                         size_t left = cur->size - size;
  290.                         //split the block if its big enough to hold another value
  291.                         if (left > (sizeof(memhdr_t) + 64)) {
  292.                             memhdr_t * split = (memhdr_t*)(((char*)cur) + size);
  293.                             split->size = left;
  294.                             split->isunused = true;
  295.                             split->next = cur->next;
  296.                             split->min = ((char*)split) + sizeof(memhdr_t);
  297.                             split->max = ((char*)split) + split->size - sizeof(char*);
  298.                             split->plock.unlock();
  299.                             cur->size = size;
  300.                             cur->max = ((char*)cur) + cur->size - sizeof(char*);
  301.                             cur->next = split;
  302.                             pcur = split;
  303.                         }
  304.                         left = cur->size / sizeof(memhdr_t);
  305.                         size_t y = (cur - pool) / sizeof(memhdr_t);
  306.                         left += y;
  307.                         for (size_t x = y; x < left; x++) {
  308.                             memcar[x] = cur;
  309.                         }
  310.                         cur->isunused = false;
  311.                         cur->mark = false;
  312.                         cur->plock.unlock();
  313.                         ++num_objects;
  314.                         return (void*)cur->min;
  315.                     }
  316.                 }
  317.                 prev = cur;
  318.                 cur = cur->next;
  319.                 prev->plock.unlock();
  320.             } else {
  321.                 cur = cur->next;
  322.             }
  323.         } while (cur != start);
  324.         if (firstry) {
  325.             firstry = false;
  326.             GCCollect();
  327.             goto secondtry;
  328.         }
  329.     }
  330.     return NULL;
  331. }
  332.  
  333.  
  334. void GCInit(void) {
  335.     pool = (memhdr_t*)calloc(MEMORY_POOL_SIZE + sizeof(memhdr_t) + 1, 1);
  336.     memcar = (memhdr_t**)calloc(MEMORY_POOL_SIZE / sizeof(memhdr_t), sizeof(memhdr_t*));
  337.  
  338.     if (pool && memcar) {
  339.         pool->size = MEMORY_POOL_SIZE;
  340.         pool->next = pool;
  341.         pool->isunused = true;
  342.         ps = pool->min = ((char*)pool) + sizeof(memhdr_t);
  343.         pe = pool->max = pool->min + MEMORY_POOL_SIZE - sizeof(char*);
  344.         pool->plock.unlock();
  345.     }
  346.     pcur = pool;
  347.     num_objects = 0;
  348. }
  349.  
  350. void GCShutdown(void) {
  351.     free(pool);
  352.     free(memcar);
  353.     pool = NULL;
  354.     memcar = NULL;
  355.     pcur = NULL;
  356.     ps = pe = NULL;
  357.     num_objects = 0;
  358. }
  359.  
  360. void GCRegisterRoot(thread_id_t id, char * min, char * max) {
  361.     rlock.lock();
  362.     for (int i = 0; i < num_roots; i++) {
  363.         if (memcmp(&(roots[i].tid), &id, sizeof(thread_id_t)) == 0) {
  364.             roots[i].min = min;
  365.             roots[i].max = max - sizeof(char*);
  366.             rlock.unlock();
  367.             return;
  368.         }
  369.     }
  370.     if (num_roots % 10 == 0) {
  371.         if (num_roots == 0) {
  372.             GCInit();
  373.         }
  374.         int nr = (num_roots / 10 + 1) * 10 + 1;
  375.         memroot_t * tmp = roots;
  376.         roots = (memroot_t*)calloc(nr, sizeof(memroot_t));
  377.         if (tmp) {
  378.             memcpy(roots, tmp, sizeof(memroot_t)*num_roots);
  379.             free(tmp);
  380.         }
  381.     }
  382.     roots[num_roots].min = min;
  383.     roots[num_roots].max = max - sizeof(char*);
  384.     roots[num_roots].thread = OpenThread(THREAD_ALL_ACCESS, FALSE, id.tid);
  385.     memcpy(&(roots[num_roots].tid), &id, sizeof(thread_id_t));
  386.     roots[num_roots++].gcnext = NULL;
  387.     rlock.unlock();
  388. }
  389.  
  390. void GCUnregisterRoot(thread_id_t id) {
  391.     rlock.lock();
  392.     if (num_roots == 1) {
  393.         GCShutdown();
  394.         CloseHandle(roots[0].thread);
  395.         free(roots);
  396.         roots = NULL;
  397.     } else {
  398.         for (int i = 0; i < num_roots; i++) {
  399.             if (memcmp(&(roots[i].tid), &id, sizeof(thread_id_t))) {
  400.                 continue;
  401.             }
  402.             CloseHandle(roots[num_roots].thread);
  403.             for (int j = i; j < num_roots; j++) {
  404.                 memcpy(&(roots[j]), &(roots[j + 1]), sizeof(memroot_t));
  405.             }
  406.             break;
  407.         }
  408.         num_roots--;
  409.     }
  410.     rlock.unlock();
  411. }
  412.  
  413. void GCFree(void * ptr) {
  414.     if (ptr) {
  415.         memhdr_t * hdr = (memhdr_t*)(((char*)ptr) - sizeof(memhdr_t));
  416.         if (rlock.trylock() && hdr->min == ptr && hdr->plock.trylock()) {
  417.             hdr->isunused = false;
  418.             rlock.unlock();
  419.             hdr->plock.unlock();
  420.         }
  421.     }
  422. }
  423.  
  424. void * operator new(size_t size){
  425.     return GCAlloc(size);
  426. }
  427.  
  428. void * operator new[](size_t size) {
  429.     return GCAlloc(size);
  430. }
  431.  
  432. void operator delete(void * ptr) {
  433.     GCFree(ptr);
  434. }
  435.  
  436. void operator delete[](void * ptr) {
  437.     GCFree(ptr);
  438. }
  439.  
  440.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 17 Beiträge ]  Gehe zu Seite Vorherige  1, 2
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 4 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.064s | 19 Queries | GZIP : On ]