Portable lock-free data structures by Keir Fraser (MCAS)
[openafs.git] / src / mcas / gc.c
1 /******************************************************************************
2  * gc.c
3  *
4  * A fully recycling epoch-based garbage collector. Works by counting
5  * threads in and out of critical regions, to work out when
6  * garbage queues can be fully deleted.
7  *
8  * Copyright (c) 2001-2003, K A Fraser
9
10 Redistribution and use in source and binary forms, with or without
11 modification, are permitted provided that the following conditions are
12 met:
13
14     * Redistributions of source code must retain the above copyright
15     * notice, this list of conditions and the following disclaimer.
16     * Redistributions in binary form must reproduce the above
17     * copyright notice, this list of conditions and the following
18     * disclaimer in the documentation and/or other materials provided
19     * with the distribution.  Neither the name of the Keir Fraser
20     * nor the names of its contributors may be used to endorse or
21     * promote products derived from this software without specific
22     * prior written permission.
23
24 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
27 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
28 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
29 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
30 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
34 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35  */
36
37 #include <assert.h>
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <string.h>
41 #include <sys/mman.h>
42 #include <unistd.h>
43 #include "portable_defns.h"
44 #include "gc.h"
45
46 /*#define MINIMAL_GC*/
47 /*#define YIELD_TO_HELP_PROGRESS*/
48 #define PROFILE_GC
49
50 /* Recycled nodes are filled with this value if WEAK_MEM_ORDER. */
51 #define INVALID_BYTE 0
52 #define INITIALISE_NODES(_p,_c) memset((_p), INVALID_BYTE, (_c));
53
54 /* Number of unique block sizes we can deal with. */
55 #define MAX_SIZES 20
56
57 #define MAX_HOOKS 4
58
59 /*
60  * The initial number of allocation chunks for each per-blocksize list.
61  * Popular allocation lists will steadily increase the allocation unit
62  * in line with demand.
63  */
64 #define ALLOC_CHUNKS_PER_LIST 10
65
66 /*
67  * How many times should a thread call gc_enter(), seeing the same epoch
68  * each time, before it makes a reclaim attempt?
69  */
70 #define ENTRIES_PER_RECLAIM_ATTEMPT 100
71
72 /*
73  *  0: current epoch -- threads are moving to this;
74  * -1: some threads may still throw garbage into this epoch;
75  * -2: no threads can see this epoch => we can zero garbage lists;
76  * -3: all threads see zeros in these garbage lists => move to alloc lists.
77  */
78 #ifdef WEAK_MEM_ORDER
79 #define NR_EPOCHS 4
80 #else
81 #define NR_EPOCHS 3
82 #endif
83
84 /*
85  * A chunk amortises the cost of allocation from shared lists. It also
86  * helps when zeroing nodes, as it increases per-cacheline pointer density
87  * and means that node locations don't need to be brought into the cache
88  * (most architectures have a non-temporal store instruction).
89  */
90 #define BLKS_PER_CHUNK 100
91 typedef struct chunk_st chunk_t;
92 struct chunk_st
93 {
94     chunk_t *next;             /* chunk chaining                 */
95     unsigned int i;            /* the next entry in blk[] to use */
96     void *blk[BLKS_PER_CHUNK];
97 };
98
99 static struct gc_global_st
100 {
101     CACHE_PAD(0);
102
103     /* The current epoch. */
104     VOLATILE unsigned int current;
105     CACHE_PAD(1);
106
107     /* Exclusive access to gc_reclaim(). */
108     VOLATILE unsigned int inreclaim;
109     CACHE_PAD(2);
110
111     /*
112      * RUN-TIME CONSTANTS (to first approximation)
113      */
114
115     /* Memory page size, in bytes. */
116     unsigned int page_size;
117
118     /* Node sizes (run-time constants). */
119     int nr_sizes;
120     int blk_sizes[MAX_SIZES];
121
122     /* Registered epoch hooks. */
123     int nr_hooks;
124     hook_fn_t hook_fns[MAX_HOOKS];
125     CACHE_PAD(3);
126
127     /*
128      * DATA WE MAY HIT HARD
129      */
130
131     /* Chain of free, empty chunks. */
132     chunk_t * VOLATILE free_chunks;
133
134     /* Main allocation lists. */
135     chunk_t * VOLATILE alloc[MAX_SIZES];
136     VOLATILE unsigned int alloc_size[MAX_SIZES];
137 #ifdef PROFILE_GC
138     VOLATILE unsigned int total_size;
139     VOLATILE unsigned int allocations;
140 #endif
141 } gc_global;
142
143
144 /* Per-thread state. */
145 struct gc_st
146 {
147     /* Epoch that this thread sees. */
148     unsigned int epoch;
149
150     /* Number of calls to gc_entry() since last gc_reclaim() attempt. */
151     unsigned int entries_since_reclaim;
152
153 #ifdef YIELD_TO_HELP_PROGRESS
154     /* Number of calls to gc_reclaim() since we last yielded. */
155     unsigned int reclaim_attempts_since_yield;
156 #endif
157
158     /* Used by gc_async_barrier(). */
159     void *async_page;
160     int   async_page_state;
161
162     /* Garbage lists. */
163     chunk_t *garbage[NR_EPOCHS][MAX_SIZES];
164     chunk_t *garbage_tail[NR_EPOCHS][MAX_SIZES];
165     chunk_t *chunk_cache;
166
167     /* Local allocation lists. */
168     chunk_t *alloc[MAX_SIZES];
169     unsigned int alloc_chunks[MAX_SIZES];
170
171     /* Hook pointer lists. */
172     chunk_t *hook[NR_EPOCHS][MAX_HOOKS];
173 };
174
175
176 #define MEM_FAIL(_s)                                                         \
177 do {                                                                         \
178     fprintf(stderr, "OUT OF MEMORY: %d bytes at line %d\n", (_s), __LINE__); \
179     exit(1);                                                                 \
180 } while ( 0 )
181
182
183 /* Allocate more empty chunks from the heap. */
184 #define CHUNKS_PER_ALLOC 1000
185 static chunk_t *alloc_more_chunks(void)
186 {
187     int i;
188     chunk_t *h, *p;
189
190     h = p = ALIGNED_ALLOC(CHUNKS_PER_ALLOC * sizeof(*h));
191     if ( h == NULL ) MEM_FAIL(CHUNKS_PER_ALLOC * sizeof(*h));
192
193     for ( i = 1; i < CHUNKS_PER_ALLOC; i++ )
194     {
195         p->next = p + 1;
196         p++;
197     }
198
199     p->next = h;
200
201     return(h);
202 }
203
204
205 /* Put a chain of chunks onto a list. */
206 static void add_chunks_to_list(chunk_t *ch, chunk_t *head)
207 {
208     chunk_t *h_next, *new_h_next, *ch_next;
209     ch_next    = ch->next;
210     new_h_next = head->next;
211     do { ch->next = h_next = new_h_next; WMB_NEAR_CAS(); }
212     while ( (new_h_next = CASPO(&head->next, h_next, ch_next)) != h_next );
213 }
214
215
216 /* Allocate a chain of @n empty chunks. Pointers may be garbage. */
217 static chunk_t *get_empty_chunks(int n)
218 {
219     int i;
220     chunk_t *new_rh, *rh, *rt, *head;
221
222  retry:
223     head = gc_global.free_chunks;
224     new_rh = head->next;
225     do {
226         rh = new_rh;
227         rt = head;
228         WEAK_DEP_ORDER_RMB();
229         for ( i = 0; i < n; i++ )
230         {
231             if ( (rt = rt->next) == head )
232             {
233                 /* Allocate some more chunks. */
234                 add_chunks_to_list(alloc_more_chunks(), head);
235                 goto retry;
236             }
237         }
238     }
239     while ( (new_rh = CASPO(&head->next, rh, rt->next)) != rh );
240
241     rt->next = rh;
242     return(rh);
243 }
244
245
246 /* Get @n filled chunks, pointing at blocks of @sz bytes each. */
247 static chunk_t *get_filled_chunks(int n, int sz)
248 {
249     chunk_t *h, *p;
250     char *node;
251     int i;
252
253 #ifdef PROFILE_GC
254     ADD_TO(gc_global.total_size, n * BLKS_PER_CHUNK * sz);
255     ADD_TO(gc_global.allocations, 1);
256 #endif
257
258     node = ALIGNED_ALLOC(n * BLKS_PER_CHUNK * sz);
259     if ( node == NULL ) MEM_FAIL(n * BLKS_PER_CHUNK * sz);
260 #ifdef WEAK_MEM_ORDER
261     INITIALISE_NODES(node, n * BLKS_PER_CHUNK * sz);
262 #endif
263
264     h = p = get_empty_chunks(n);
265     do {
266         p->i = BLKS_PER_CHUNK;
267         for ( i = 0; i < BLKS_PER_CHUNK; i++ )
268         {
269             p->blk[i] = node;
270             node += sz;
271         }
272     }
273     while ( (p = p->next) != h );
274
275     return(h);
276 }
277
278
279 /*
280  * gc_async_barrier: Cause an asynchronous barrier in all other threads. We do
281  * this by causing a TLB shootdown to be propagated to all other processors.
282  * Each time such an action is required, this function calls:
283  *   mprotect(async_page, <page size>, <new flags>)
284  * Each thread's state contains a memory page dedicated for this purpose.
285  */
286 #ifdef WEAK_MEM_ORDER
287 static void gc_async_barrier(gc_t *gc)
288 {
289     mprotect(gc->async_page, gc_global.page_size,
290              gc->async_page_state ? PROT_READ : PROT_NONE);
291     gc->async_page_state = !gc->async_page_state;
292 }
293 #else
294 #define gc_async_barrier(_g) ((void)0)
295 #endif
296
297
298 /* Grab a level @i allocation chunk from main chain. */
299 static chunk_t *get_alloc_chunk(gc_t *gc, int i)
300 {
301     chunk_t *alloc, *p, *new_p, *nh;
302     unsigned int sz;
303
304     alloc = gc_global.alloc[i];
305     new_p = alloc->next;
306
307     do {
308         p = new_p;
309         while ( p == alloc )
310         {
311             sz = gc_global.alloc_size[i];
312             nh = get_filled_chunks(sz, gc_global.blk_sizes[i]);
313             ADD_TO(gc_global.alloc_size[i], sz >> 3);
314             gc_async_barrier(gc);
315             add_chunks_to_list(nh, alloc);
316             p = alloc->next;
317         }
318         WEAK_DEP_ORDER_RMB();
319     }
320     while ( (new_p = CASPO(&alloc->next, p, p->next)) != p );
321
322     p->next = p;
323     assert(p->i == BLKS_PER_CHUNK);
324     return(p);
325 }
326
327
328 #ifndef MINIMAL_GC
329 /*
330  * gc_reclaim: Scans the list of struct gc_perthread looking for the lowest
331  * maximum epoch number seen by a thread that's in the list code. If it's the
332  * current epoch, the "nearly-free" lists from the previous epoch are
333  * reclaimed, and the epoch is incremented.
334  */
335 static void gc_reclaim(void)
336 {
337     ptst_t       *ptst, *first_ptst, *our_ptst = NULL;
338     gc_t         *gc = NULL;
339     unsigned long curr_epoch;
340     chunk_t      *ch, *t;
341     int           two_ago, three_ago, i, j;
342  
343     /* Barrier to entering the reclaim critical section. */
344     if ( gc_global.inreclaim || CASIO(&gc_global.inreclaim, 0, 1) ) return;
345
346     /*
347      * Grab first ptst structure *before* barrier -- prevent bugs
348      * on weak-ordered architectures.
349      */
350     first_ptst = ptst_first();
351     MB();
352     curr_epoch = gc_global.current;
353
354     /* Have all threads seen the current epoch, or not in mutator code? */
355     for ( ptst = first_ptst; ptst != NULL; ptst = ptst_next(ptst) )
356     {
357         if ( (ptst->count > 1) && (ptst->gc->epoch != curr_epoch) ) goto out;
358     }
359
360     /*
361      * Three-epoch-old garbage lists move to allocation lists.
362      * Two-epoch-old garbage lists are cleaned out.
363      */
364     two_ago   = (curr_epoch+2) % NR_EPOCHS;
365     three_ago = (curr_epoch+1) % NR_EPOCHS;
366     if ( gc_global.nr_hooks != 0 )
367         our_ptst = (ptst_t *)pthread_getspecific(ptst_key);
368     for ( ptst = first_ptst; ptst != NULL; ptst = ptst_next(ptst) )
369     {
370         gc = ptst->gc;
371
372         for ( i = 0; i < gc_global.nr_sizes; i++ )
373         {
374 #ifdef WEAK_MEM_ORDER
375             int sz = gc_global.blk_sizes[i];
376             if ( gc->garbage[two_ago][i] != NULL )
377             {
378                 chunk_t *head = gc->garbage[two_ago][i];
379                 ch = head;
380                 do {
381                     int j;
382                     for ( j = 0; j < ch->i; j++ )
383                         INITIALISE_NODES(ch->blk[j], sz);
384                 }
385                 while ( (ch = ch->next) != head );
386             }
387 #endif
388
389             /* NB. Leave one chunk behind, as it is probably not yet full. */
390             t = gc->garbage[three_ago][i];
391             if ( (t == NULL) || ((ch = t->next) == t) ) continue;
392             gc->garbage_tail[three_ago][i]->next = ch;
393             gc->garbage_tail[three_ago][i] = t;
394             t->next = t;
395             add_chunks_to_list(ch, gc_global.alloc[i]);
396         }
397
398         for ( i = 0; i < gc_global.nr_hooks; i++ )
399         {
400             hook_fn_t fn = gc_global.hook_fns[i];
401             ch = gc->hook[three_ago][i];
402             if ( ch == NULL ) continue;
403             gc->hook[three_ago][i] = NULL;
404
405             t = ch;
406             do { for ( j = 0; j < t->i; j++ ) fn(our_ptst, t->blk[j]); }
407             while ( (t = t->next) != ch );
408
409             add_chunks_to_list(ch, gc_global.free_chunks);
410         }
411     }
412
413     /* Update current epoch. */
414     WMB();
415     gc_global.current = (curr_epoch+1) % NR_EPOCHS;
416
417  out:
418     gc_global.inreclaim = 0;
419 }
420 #endif /* MINIMAL_GC */
421
422
423 void *gc_alloc(ptst_t *ptst, int alloc_id)
424 {
425     gc_t *gc = ptst->gc;
426     chunk_t *ch;
427
428     ch = gc->alloc[alloc_id];
429     if ( ch->i == 0 )
430     {
431         if ( gc->alloc_chunks[alloc_id]++ == 100 )
432         {
433             gc->alloc_chunks[alloc_id] = 0;
434             add_chunks_to_list(ch, gc_global.free_chunks);
435             gc->alloc[alloc_id] = ch = get_alloc_chunk(gc, alloc_id);
436         }
437         else
438         {
439             chunk_t *och = ch;
440             ch = get_alloc_chunk(gc, alloc_id);
441             ch->next  = och->next;
442             och->next = ch;
443             gc->alloc[alloc_id] = ch;
444         }
445     }
446
447     return ch->blk[--ch->i];
448 }
449
450
451 static chunk_t *chunk_from_cache(gc_t *gc)
452 {
453     chunk_t *ch = gc->chunk_cache, *p = ch->next;
454
455     if ( ch == p )
456     {
457         gc->chunk_cache = get_empty_chunks(100);
458     }
459     else
460     {
461         ch->next = p->next;
462         p->next  = p;
463     }
464
465     p->i = 0;
466     return(p);
467 }
468
469
470 void gc_free(ptst_t *ptst, void *p, int alloc_id)
471 {
472 #ifndef MINIMAL_GC
473     gc_t *gc = ptst->gc;
474     chunk_t *prev, *new, *ch = gc->garbage[gc->epoch][alloc_id];
475
476     if ( ch == NULL )
477     {
478         gc->garbage[gc->epoch][alloc_id] = ch = chunk_from_cache(gc);
479         gc->garbage_tail[gc->epoch][alloc_id] = ch;
480     }
481     else if ( ch->i == BLKS_PER_CHUNK )
482     {
483         prev = gc->garbage_tail[gc->epoch][alloc_id];
484         new  = chunk_from_cache(gc);
485         gc->garbage[gc->epoch][alloc_id] = new;
486         new->next  = ch;
487         prev->next = new;
488         ch = new;
489     }
490
491     ch->blk[ch->i++] = p;
492 #endif
493 }
494
495
496 void gc_add_ptr_to_hook_list(ptst_t *ptst, void *ptr, int hook_id)
497 {
498     gc_t *gc = ptst->gc;
499     chunk_t *och, *ch = gc->hook[gc->epoch][hook_id];
500
501     if ( ch == NULL )
502     {
503         gc->hook[gc->epoch][hook_id] = ch = chunk_from_cache(gc);
504     }
505     else
506     {
507         ch = ch->next;
508         if ( ch->i == BLKS_PER_CHUNK )
509         {
510             och       = gc->hook[gc->epoch][hook_id];
511             ch        = chunk_from_cache(gc);
512             ch->next  = och->next;
513             och->next = ch;
514         }
515     }
516
517     ch->blk[ch->i++] = ptr;
518 }
519
520
521 void gc_unsafe_free(ptst_t *ptst, void *p, int alloc_id)
522 {
523     gc_t *gc = ptst->gc;
524     chunk_t *ch;
525
526     ch = gc->alloc[alloc_id];
527     if ( ch->i < BLKS_PER_CHUNK )
528     {
529         ch->blk[ch->i++] = p;
530     }
531     else
532     {
533         gc_free(ptst, p, alloc_id);
534     }
535 }
536
537
538 void gc_enter(ptst_t *ptst)
539 {
540 #ifdef MINIMAL_GC
541     ptst->count++;
542     MB();
543 #else
544     gc_t *gc = ptst->gc;
545     int new_epoch, cnt;
546
547  retry:
548     cnt = ptst->count++;
549     MB();
550     if ( cnt == 1 )
551     {
552         new_epoch = gc_global.current;
553         if ( gc->epoch != new_epoch )
554         {
555             gc->epoch = new_epoch;
556             gc->entries_since_reclaim        = 0;
557 #ifdef YIELD_TO_HELP_PROGRESS
558             gc->reclaim_attempts_since_yield = 0;
559 #endif
560         }
561         else if ( gc->entries_since_reclaim++ == 100 )
562         {
563             ptst->count--;
564 #ifdef YIELD_TO_HELP_PROGRESS
565             if ( gc->reclaim_attempts_since_yield++ == 10000 )
566             {
567                 gc->reclaim_attempts_since_yield = 0;
568                 sched_yield();
569             }
570 #endif
571             gc->entries_since_reclaim = 0;
572             gc_reclaim();
573             goto retry;
574         }
575     }
576 #endif
577 }
578
579
580 void gc_exit(ptst_t *ptst)
581 {
582     MB();
583     ptst->count--;
584 }
585
586
587 gc_t *gc_init(void)
588 {
589     gc_t *gc;
590     int   i;
591
592     gc = ALIGNED_ALLOC(sizeof(*gc));
593     if ( gc == NULL ) MEM_FAIL(sizeof(*gc));
594     memset(gc, 0, sizeof(*gc));
595
596 #ifdef WEAK_MEM_ORDER
597     /* Initialise shootdown state. */
598     gc->async_page = mmap(NULL, gc_global.page_size, PROT_NONE,
599                           MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
600     if ( gc->async_page == (void *)MAP_FAILED ) MEM_FAIL(gc_global.page_size);
601     gc->async_page_state = 1;
602 #endif
603
604     gc->chunk_cache = get_empty_chunks(100);
605
606     /* Get ourselves a set of allocation chunks. */
607     for ( i = 0; i < gc_global.nr_sizes; i++ )
608     {
609         gc->alloc[i] = get_alloc_chunk(gc, i);
610     }
611     for ( ; i < MAX_SIZES; i++ )
612     {
613         gc->alloc[i] = chunk_from_cache(gc);
614     }
615
616     return(gc);
617 }
618
619
620 int gc_add_allocator(int alloc_size)
621 {
622     int ni, i = gc_global.nr_sizes;
623     while ( (ni = CASIO(&gc_global.nr_sizes, i, i+1)) != i ) i = ni;
624     gc_global.blk_sizes[i]  = alloc_size;
625     gc_global.alloc_size[i] = ALLOC_CHUNKS_PER_LIST;
626     gc_global.alloc[i] = get_filled_chunks(ALLOC_CHUNKS_PER_LIST, alloc_size);
627     return i;
628 }
629
630
631 void gc_remove_allocator(int alloc_id)
632 {
633     /* This is a no-op for now. */
634 }
635
636
637 int gc_add_hook(hook_fn_t fn)
638 {
639     int ni, i = gc_global.nr_hooks;
640     while ( (ni = CASIO(&gc_global.nr_hooks, i, i+1)) != i ) i = ni;
641     gc_global.hook_fns[i] = fn;
642     return i;
643 }
644
645
646 void gc_remove_hook(int hook_id)
647 {
648     /* This is a no-op for now. */
649 }
650
651
652 void _destroy_gc_subsystem(void)
653 {
654 #ifdef PROFILE_GC
655     printf("Total heap: %u bytes (%.2fMB) in %u allocations\n",
656            gc_global.total_size, (double)gc_global.total_size / 1000000,
657            gc_global.allocations);
658 #endif
659 }
660
661
662 void _init_gc_subsystem(void)
663 {
664     memset(&gc_global, 0, sizeof(gc_global));
665
666     gc_global.page_size   = (unsigned int)sysconf(_SC_PAGESIZE);
667     gc_global.free_chunks = alloc_more_chunks();
668
669     gc_global.nr_hooks = 0;
670     gc_global.nr_sizes = 0;
671 }