From f14806f88b7ad7fa72d867bb52e321a2d2a2ef07 Mon Sep 17 00:00:00 2001 From: Robert Haas Date: Fri, 3 Aug 2012 12:15:11 +0000 Subject: [PATCH] Refactor garbage collection logic into a separate subroutine. --- src/backend/utils/hash/chash.c | 231 ++++++++++++++++++--------------- 1 file changed, 126 insertions(+), 105 deletions(-) diff --git a/src/backend/utils/hash/chash.c b/src/backend/utils/hash/chash.c index 7169d85a8d..36a619babe 100644 --- a/src/backend/utils/hash/chash.c +++ b/src/backend/utils/hash/chash.c @@ -213,6 +213,7 @@ char *CHashStatisticsNames[] = { /* Function prototypes. */ static CHashPtr CHashAllocate(CHashTable table); +static CHashPtr CHashAllocateViaGC(CHashTable table); static void CHashAddToGarbage(CHashTable table, uint32 bucket, CHashPtr c); static void CHashBucketScan(CHashTable table, CHashPtr *start, @@ -807,7 +808,6 @@ CHashAllocate(CHashTable table) uint32 f_home = ((uint32) MyBackendId) % table->nfreelists; uint32 f_current = f_home; CHashPtr new; - CHashPtr garbage; /* If this process hasn't initialized gc_next yet, do that now. */ if (table->gc_pid != MyProcPid) @@ -856,121 +856,142 @@ CHashAllocate(CHashTable table) new = *b; } - /* If next garbage list is non-empty, empty it via compare-and-swap. */ - table->gc_next = (table->gc_next + 1) % table->ngarbage; - b = &table->garbage[table->gc_next]; - garbage = *b; - if (CHashPtrIsInvalid(garbage)) - ; - else if (!__sync_bool_compare_and_swap(b, garbage, InvalidCHashPtr)) - CHashTableIncrementStatistic(table, CHS_Garbage_Dequeue_Fail); - else - { - uint32 i; - CHashPtr fhead; - CHashNode *n; - CHashPtr *fh = &table->freelist[f_home]; + /* Attempt garbage collection. */ + new = CHashAllocateViaGC(table); + if (!CHashPtrIsInvalid(new)) + return new; - /* - * Before removing elements removed from the garbage list to the - * freelist, we must wait until (1) all bucket scans that might - * still see elements on the freelist as part of the bucket chain - * have completed and (2) all allocations that might see an old - * version of the freelist containing one of the elements to be - * garbage collected have completed. - * - * Note: We can't begin this operation until the clearing of the - * garbage list has been committed to memory, but since that was - * done using an atomic operation no explicit barrier is needed - * here. - * - * Note: We could have a "soft" version of this that merely - * requeues the garbage if it's not immediately recycleable, but - * it's not clear that we need such a thing. On the flip side we - * might want to eventually enter a longer sleep here, or PANIC, - * but it's not clear exactly how to calibrate that. - */ - CHashTableIncrementStatistic(table, CHS_GC); - MyProc->hazard[0] = NULL; - for (i = 0; i < ProcGlobal->allProcCount; i++) - { - volatile PGPROC *proc = &ProcGlobal->allProcs[i]; - void *hazard; + /* Advance to next freelist. */ + f_current = (f_current + 1) % table->nfreelists; + } +} - hazard = proc->hazard[0]; - if (hazard == b || hazard == fh) - { - CHashTableIncrementStatistic(table, CHS_GC_Spin); - do - { - hazard = proc->hazard[0]; - } while (hazard == b || hazard == fh); - } - } +/* + * Attempt to satisfy an allocation request via garbage collection. + */ +static CHashPtr +CHashAllocateViaGC(CHashTable table) +{ + uint32 f_home = ((uint32) MyBackendId) % table->nfreelists; + CHashPtr *b; + CHashPtr *fh = &table->freelist[f_home]; + CHashPtr fhead; + CHashPtr garbage; + CHashPtr new; + CHashNode *n; + uint32 i; - /* Remove one item from list to satisfy current allocation. */ - new = garbage; - n = CHashTableGetNode(table, new); - pg_read_barrier_depends(); - fhead = n->un.gcnext; + /* Select target garbage list. */ + table->gc_next = (table->gc_next + 1) % table->ngarbage; + b = &table->garbage[table->gc_next]; + garbage = *b; - if (CHashPtrIsInvalid(fhead)) - { - /* - * We have reclaimed exactly node, so there's nothing to put - * back on the free list. In this case (only) we need a - * memory barrier, because the reads above must complete - * before we overwrite n->un.gcnext with a new hashcode. - * (This is only needed when we reclaim exactly one node, - * because in any other case we'll do a compare-and-swap - * before returning, which implies a full barrier.) - */ - pg_memory_barrier(); - CHashTableIncrementStatistic(table, CHS_GC_Reclaim_Skipped); - } - else if (__sync_bool_compare_and_swap(fh, InvalidCHashPtr, fhead)) - { - /* - * Our free list is empty, and we've succesfully pushed the - * reclaimed nodes onto it. So we're done. - */ - CHashTableIncrementStatistic(table, CHS_GC_Reclaim_Fast); - } - else + /* If list is empty, fail. */ + if (CHashPtrIsInvalid(garbage)) + return InvalidCHashPtr; + + /* If we're unable to empty the list via compare-and-swap, fail. */ + if (!__sync_bool_compare_and_swap(b, garbage, InvalidCHashPtr)) + { + CHashTableIncrementStatistic(table, CHS_Garbage_Dequeue_Fail); + return InvalidCHashPtr; + } + + /* + * Before removing elements removed from the garbage list to the + * freelist, we must wait until (1) all bucket scans that might + * still see elements on the freelist as part of the bucket chain + * have completed and (2) all allocations that might see an old + * version of the freelist containing one of the elements to be + * garbage collected have completed. + * + * Note: We can't begin this operation until the clearing of the + * garbage list has been committed to memory, but since that was + * done using an atomic operation no explicit barrier is needed + * here. + * + * Note: We could have a "soft" version of this that merely + * requeues the garbage if it's not immediately recycleable, but + * it's not clear that we need such a thing. On the flip side we + * might want to eventually enter a longer sleep here, or PANIC, + * but it's not clear exactly how to calibrate that. + */ + CHashTableIncrementStatistic(table, CHS_GC); + MyProc->hazard[0] = NULL; + for (i = 0; i < ProcGlobal->allProcCount; i++) + { + volatile PGPROC *proc = &ProcGlobal->allProcs[i]; + void *hazard; + + hazard = proc->hazard[0]; + if (hazard == b || hazard == fh) + { + CHashTableIncrementStatistic(table, CHS_GC_Spin); + do { - CHashPtr fcurrent; - CHashPtr fnext; - CHashPtr oldhead; + hazard = proc->hazard[0]; + } while (hazard == b || hazard == fh); + } + } - /* Walk list of reclaimed elements to end. */ - fcurrent = fhead; - for (;;) - { - n = CHashTableGetNode(table, fcurrent); - fnext = n->un.gcnext; - if (CHashPtrIsInvalid(fnext)) - break; - fcurrent = fnext; - } + /* Remove one item from list to satisfy current allocation. */ + new = garbage; + n = CHashTableGetNode(table, new); + pg_read_barrier_depends(); + fhead = n->un.gcnext; - /* Push reclaimed elements onto home free list. */ - for (;;) - { - oldhead = *fh; - n->un.gcnext = oldhead; - if (__sync_bool_compare_and_swap(fh, oldhead, fhead)) - break; - CHashTableIncrementStatistic(table, CHS_GC_Reclaim_Retry); - } - } + if (CHashPtrIsInvalid(fhead)) + { + /* + * We have reclaimed exactly node, so there's nothing to put + * back on the free list. In this case (only) we need a + * memory barrier, because the reads above must complete + * before we overwrite n->un.gcnext with a new hashcode. + * (This is only needed when we reclaim exactly one node, + * because in any other case we'll do a compare-and-swap + * before returning, which implies a full barrier.) + */ + pg_memory_barrier(); + CHashTableIncrementStatistic(table, CHS_GC_Reclaim_Skipped); + } + else if (__sync_bool_compare_and_swap(fh, InvalidCHashPtr, fhead)) + { + /* + * Our free list is empty, and we've succesfully pushed the + * reclaimed nodes onto it. So we're done. + */ + CHashTableIncrementStatistic(table, CHS_GC_Reclaim_Fast); + } + else + { + CHashPtr fcurrent; + CHashPtr fnext; + CHashPtr oldhead; - /* Return the element we saved for ourselves. */ - return new; + /* Walk list of reclaimed elements to end. */ + fcurrent = fhead; + for (;;) + { + n = CHashTableGetNode(table, fcurrent); + fnext = n->un.gcnext; + if (CHashPtrIsInvalid(fnext)) + break; + fcurrent = fnext; } - /* Advance to next freelist. */ - f_current = (f_current + 1) % table->nfreelists; + /* Push reclaimed elements onto home free list. */ + for (;;) + { + oldhead = *fh; + n->un.gcnext = oldhead; + if (__sync_bool_compare_and_swap(fh, oldhead, fhead)) + break; + CHashTableIncrementStatistic(table, CHS_GC_Reclaim_Retry); + } } + + /* Return the element we saved for ourselves. */ + return new; } /* -- 2.39.5