libgo/runtime/mfinal.c

   1 // Copyright 2010 The Go Authors.  All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 #include "runtime.h"
   6 #include "malloc.h"
   7
   8 static Lock finlock;
   9
  10 void
  11 runtime_initfintab()
  12 {
  13         runtime_initlock(&finlock);
  14 }
  15
  16 // Finalizer hash table.  Direct hash, linear scan, at most 3/4 full.
  17 // Table size is power of 3 so that hash can be key % max.
  18 // Key[i] == (void*)-1 denotes free but formerly occupied entry
  19 // (doesn't stop the linear scan).
  20 // Key and val are separate tables because the garbage collector
  21 // must be instructed to ignore the pointers in key but follow the
  22 // pointers in val.
  23 typedef struct Fintab Fintab;
  24 struct Fintab
  25 {
  26         void **key;
  27         Finalizer **val;
  28         int32 nkey;     // number of non-nil entries in key
  29         int32 ndead;    // number of dead (-1) entries in key
  30         int32 max;      // size of key, val allocations
  31 };
  32
  33 static void
  34 addfintab(Fintab *t, void *k, Finalizer *v)
  35 {
  36         int32 i, j;
  37
  38         i = (uintptr)k % (uintptr)t->max;
  39         for(j=0; j<t->max; j++) {
  40                 if(t->key[i] == nil) {
  41                         t->nkey++;
  42                         goto ret;
  43                 }
  44                 if(t->key[i] == (void*)-1) {
  45                         t->ndead--;
  46                         goto ret;
  47                 }
  48                 if(++i == t->max)
  49                         i = 0;
  50         }
  51
  52         // cannot happen - table is known to be non-full
  53         runtime_throw("finalizer table inconsistent");
  54
  55 ret:
  56         t->key[i] = k;
  57         t->val[i] = v;
  58 }
  59
  60 static Finalizer*
  61 lookfintab(Fintab *t, void *k, bool del)
  62 {
  63         int32 i, j;
  64         Finalizer *v;
  65
  66         if(t->max == 0)
  67                 return nil;
  68         i = (uintptr)k % (uintptr)t->max;
  69         for(j=0; j<t->max; j++) {
  70                 if(t->key[i] == nil)
  71                         return nil;
  72                 if(t->key[i] == k) {
  73                         v = t->val[i];
  74                         if(del) {
  75                                 t->key[i] = (void*)-1;
  76                                 t->val[i] = nil;
  77                                 t->ndead++;
  78                         }
  79                         return v;
  80                 }
  81                 if(++i == t->max)
  82                         i = 0;
  83         }
  84
  85         // cannot happen - table is known to be non-full
  86         runtime_throw("finalizer table inconsistent");
  87         return nil;
  88 }
  89
  90 static Fintab fintab;
  91
  92 // add finalizer; caller is responsible for making sure not already in table
  93 void
  94 runtime_addfinalizer(void *p, void (*f)(void*), const struct __go_func_type *ft)
  95 {
  96         Fintab newtab;
  97         int32 i;
  98         uint32 *ref;
  99         byte *base;
 100         Finalizer *e;
 101
 102         e = nil;
 103         if(f != nil) {
 104                 e = runtime_mal(sizeof *e);
 105                 e->fn = f;
 106                 e->ft = ft;
 107         }
 108
 109         if(!__sync_bool_compare_and_swap(&m->holds_finlock, 0, 1))
 110                 runtime_throw("finalizer deadlock");
 111
 112         runtime_lock(&finlock);
 113         if(!runtime_mlookup(p, &base, nil, nil, &ref) || p != base) {
 114                 runtime_unlock(&finlock);
 115                 __sync_bool_compare_and_swap(&m->holds_finlock, 1, 0);
 116                 runtime_throw("addfinalizer on invalid pointer");
 117         }
 118         if(f == nil) {
 119                 if(*ref & RefHasFinalizer) {
 120                         lookfintab(&fintab, p, 1);
 121                         *ref &= ~RefHasFinalizer;
 122                 }
 123                 goto unlock;
 124         }
 125
 126         if(*ref & RefHasFinalizer) {
 127                 runtime_unlock(&finlock);
 128                 __sync_bool_compare_and_swap(&m->holds_finlock, 1, 0);
 129                 runtime_throw("double finalizer");
 130         }
 131         *ref |= RefHasFinalizer;
 132
 133         if(fintab.nkey >= fintab.max/2+fintab.max/4) {
 134                 // keep table at most 3/4 full:
 135                 // allocate new table and rehash.
 136
 137                 runtime_memclr((byte*)&newtab, sizeof newtab);
 138                 newtab.max = fintab.max;
 139                 if(newtab.max == 0)
 140                         newtab.max = 3*3*3;
 141                 else if(fintab.ndead < fintab.nkey/2) {
 142                         // grow table if not many dead values.
 143                         // otherwise just rehash into table of same size.
 144                         newtab.max *= 3;
 145                 }
 146
 147                 newtab.key = runtime_mallocgc(newtab.max*sizeof newtab.key[0], RefNoPointers, 0, 1);
 148                 newtab.val = runtime_mallocgc(newtab.max*sizeof newtab.val[0], 0, 0, 1);
 149
 150                 for(i=0; i<fintab.max; i++) {
 151                         void *k;
 152
 153                         k = fintab.key[i];
 154                         if(k != nil && k != (void*)-1)
 155                                 addfintab(&newtab, k, fintab.val[i]);
 156                 }
 157                 runtime_free(fintab.key);
 158                 runtime_free(fintab.val);
 159                 fintab = newtab;
 160         }
 161
 162         addfintab(&fintab, p, e);
 163  unlock:
 164         runtime_unlock(&finlock);
 165
 166         __sync_bool_compare_and_swap(&m->holds_finlock, 1, 0);
 167
 168         if(__sync_bool_compare_and_swap(&m->gcing_for_finlock, 1, 0)) {
 169                 __go_run_goroutine_gc(200);
 170         }
 171 }
 172
 173 // get finalizer; if del, delete finalizer.
 174 // caller is responsible for updating RefHasFinalizer bit.
 175 Finalizer*
 176 runtime_getfinalizer(void *p, bool del)
 177 {
 178         Finalizer *f;
 179
 180         if(!__sync_bool_compare_and_swap(&m->holds_finlock, 0, 1))
 181                 runtime_throw("finalizer deadlock");
 182
 183         runtime_lock(&finlock);
 184         f = lookfintab(&fintab, p, del);
 185         runtime_unlock(&finlock);
 186
 187         __sync_bool_compare_and_swap(&m->holds_finlock, 1, 0);
 188         if(__sync_bool_compare_and_swap(&m->gcing_for_finlock, 1, 0)) {
 189                 __go_run_goroutine_gc(201);
 190         }
 191
 192         return f;
 193 }
 194
 195 void
 196 runtime_walkfintab(void (*fn)(void*), void (*scan)(byte *, int64))
 197 {
 198         void **key;
 199         void **ekey;
 200
 201         if(!__sync_bool_compare_and_swap(&m->holds_finlock, 0, 1))
 202                 runtime_throw("finalizer deadlock");
 203
 204         scan((byte*)&fintab, sizeof fintab);
 205         runtime_lock(&finlock);
 206         key = fintab.key;
 207         ekey = key + fintab.max;
 208         for(; key < ekey; key++)
 209                 if(*key != nil && *key != ((void*)-1))
 210                         fn(*key);
 211         runtime_unlock(&finlock);
 212
 213         __sync_bool_compare_and_swap(&m->holds_finlock, 1, 0);
 214         if(__sync_bool_compare_and_swap(&m->gcing_for_finlock, 1, 0)) {
 215                 runtime_throw("walkfintab not called from gc");
 216         }
 217 }