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 "arch.h"
   7 #include "malloc.h"
   8
   9 enum { debug = 0 };
  10
  11 typedef struct Fin Fin;
  12 struct Fin
  13 {
  14         void (*fn)(void*);
  15         const struct __go_func_type *ft;
  16 };
  17
  18 // Finalizer hash table.  Direct hash, linear scan, at most 3/4 full.
  19 // Table size is power of 3 so that hash can be key % max.
  20 // Key[i] == (void*)-1 denotes free but formerly occupied entry
  21 // (doesn't stop the linear scan).
  22 // Key and val are separate tables because the garbage collector
  23 // must be instructed to ignore the pointers in key but follow the
  24 // pointers in val.
  25 typedef struct Fintab Fintab;
  26 struct Fintab
  27 {
  28         Lock;
  29         void **fkey;
  30         Fin *val;
  31         int32 nkey;     // number of non-nil entries in key
  32         int32 ndead;    // number of dead (-1) entries in key
  33         int32 max;      // size of key, val allocations
  34 };
  35
  36 #define TABSZ 17
  37 #define TAB(p) (&fintab[((uintptr)(p)>>3)%TABSZ])
  38
  39 static struct {
  40         Fintab;
  41         uint8 pad[0 /* CacheLineSize - sizeof(Fintab) */];
  42 } fintab[TABSZ];
  43
  44 void
  45 runtime_initfintab()
  46 {
  47         int32 i;
  48
  49         for(i=0; i<TABSZ; i++)
  50                 runtime_initlock(&fintab[i]);
  51 }
  52
  53 static void
  54 addfintab(Fintab *t, void *k, void (*fn)(void*), const struct __go_func_type *ft)
  55 {
  56         int32 i, j;
  57
  58         i = (uintptr)k % (uintptr)t->max;
  59         for(j=0; j<t->max; j++) {
  60                 if(t->fkey[i] == nil) {
  61                         t->nkey++;
  62                         goto ret;
  63                 }
  64                 if(t->fkey[i] == (void*)-1) {
  65                         t->ndead--;
  66                         goto ret;
  67                 }
  68                 if(++i == t->max)
  69                         i = 0;
  70         }
  71
  72         // cannot happen - table is known to be non-full
  73         runtime_throw("finalizer table inconsistent");
  74
  75 ret:
  76         t->fkey[i] = k;
  77         t->val[i].fn = fn;
  78         t->val[i].ft = ft;
  79 }
  80
  81 static bool
  82 lookfintab(Fintab *t, void *k, bool del, Fin *f)
  83 {
  84         int32 i, j;
  85
  86         if(t->max == 0)
  87                 return false;
  88         i = (uintptr)k % (uintptr)t->max;
  89         for(j=0; j<t->max; j++) {
  90                 if(t->fkey[i] == nil)
  91                         return false;
  92                 if(t->fkey[i] == k) {
  93                         if(f)
  94                                 *f = t->val[i];
  95                         if(del) {
  96                                 t->fkey[i] = (void*)-1;
  97                                 t->val[i].fn = nil;
  98                                 t->val[i].ft = nil;
  99                                 t->ndead++;
 100                         }
 101                         return true;
 102                 }
 103                 if(++i == t->max)
 104                         i = 0;
 105         }
 106
 107         // cannot happen - table is known to be non-full
 108         runtime_throw("finalizer table inconsistent");
 109         return false;
 110 }
 111
 112 static void
 113 resizefintab(Fintab *tab)
 114 {
 115         Fintab newtab;
 116         void *k;
 117         int32 i;
 118
 119         runtime_memclr((byte*)&newtab, sizeof newtab);
 120         newtab.max = tab->max;
 121         if(newtab.max == 0)
 122                 newtab.max = 3*3*3;
 123         else if(tab->ndead < tab->nkey/2) {
 124                 // grow table if not many dead values.
 125                 // otherwise just rehash into table of same size.
 126                 newtab.max *= 3;
 127         }
 128
 129         newtab.fkey = runtime_mallocgc(newtab.max*sizeof newtab.fkey[0], FlagNoPointers, 0, 1);
 130         newtab.val = runtime_mallocgc(newtab.max*sizeof newtab.val[0], 0, 0, 1);
 131
 132         for(i=0; i<tab->max; i++) {
 133                 k = tab->fkey[i];
 134                 if(k != nil && k != (void*)-1)
 135                         addfintab(&newtab, k, tab->val[i].fn, tab->val[i].ft);
 136         }
 137
 138         runtime_free(tab->fkey);
 139         runtime_free(tab->val);
 140
 141         tab->fkey = newtab.fkey;
 142         tab->val = newtab.val;
 143         tab->nkey = newtab.nkey;
 144         tab->ndead = newtab.ndead;
 145         tab->max = newtab.max;
 146 }
 147
 148 bool
 149 runtime_addfinalizer(void *p, void (*f)(void*), const struct __go_func_type *ft)
 150 {
 151         Fintab *tab;
 152         byte *base;
 153         bool ret = false;
 154
 155         if(debug) {
 156                 if(!runtime_mlookup(p, &base, nil, nil) || p != base)
 157                         runtime_throw("addfinalizer on invalid pointer");
 158         }
 159
 160         if(!__sync_bool_compare_and_swap(&m->holds_finlock, 0, 1))
 161                 runtime_throw("finalizer deadlock");
 162
 163         tab = TAB(p);
 164         runtime_lock(tab);
 165         if(f == nil) {
 166                 if(lookfintab(tab, p, true, nil))
 167                         runtime_setblockspecial(p, false);
 168                 ret = true;
 169                 goto unlock;
 170         }
 171
 172         if(lookfintab(tab, p, false, nil)) {
 173                 ret = false;
 174                 goto unlock;
 175         }
 176
 177         if(tab->nkey >= tab->max/2+tab->max/4) {
 178                 // keep table at most 3/4 full:
 179                 // allocate new table and rehash.
 180                 resizefintab(tab);
 181         }
 182
 183         addfintab(tab, p, f, ft);
 184         runtime_setblockspecial(p, true);
 185         ret = true;
 186
 187  unlock:
 188         runtime_unlock(tab);
 189
 190         __sync_bool_compare_and_swap(&m->holds_finlock, 1, 0);
 191
 192         if(__sync_bool_compare_and_swap(&m->gcing_for_finlock, 1, 0)) {
 193                 __go_run_goroutine_gc(200);
 194         }
 195
 196         return ret;
 197 }
 198
 199 // get finalizer; if del, delete finalizer.
 200 // caller is responsible for updating RefHasFinalizer (special) bit.
 201 bool
 202 runtime_getfinalizer(void *p, bool del, void (**fn)(void*), const struct __go_func_type **ft)
 203 {
 204         Fintab *tab;
 205         bool res;
 206         Fin f;
 207
 208         if(!__sync_bool_compare_and_swap(&m->holds_finlock, 0, 1))
 209                 runtime_throw("finalizer deadlock");
 210
 211         tab = TAB(p);
 212         runtime_lock(tab);
 213         res = lookfintab(tab, p, del, &f);
 214         runtime_unlock(tab);
 215
 216         __sync_bool_compare_and_swap(&m->holds_finlock, 1, 0);
 217         if(__sync_bool_compare_and_swap(&m->gcing_for_finlock, 1, 0)) {
 218                 __go_run_goroutine_gc(201);
 219         }
 220
 221         if(res==false)
 222                 return false;
 223         *fn = f.fn;
 224         *ft = f.ft;
 225         return true;
 226 }
 227
 228 void
 229 runtime_walkfintab(void (*fn)(void*), void (*scan)(byte *, int64))
 230 {
 231         void **key;
 232         void **ekey;
 233         int32 i;
 234
 235         if(!__sync_bool_compare_and_swap(&m->holds_finlock, 0, 1))
 236                 runtime_throw("finalizer deadlock");
 237
 238         for(i=0; i<TABSZ; i++) {
 239                 runtime_lock(&fintab[i]);
 240                 key = fintab[i].fkey;
 241                 ekey = key + fintab[i].max;
 242                 for(; key < ekey; key++)
 243                         if(*key != nil && *key != ((void*)-1))
 244                                 fn(*key);
 245                 scan((byte*)&fintab[i].fkey, sizeof(void*));
 246                 scan((byte*)&fintab[i].val, sizeof(void*));
 247                 runtime_unlock(&fintab[i]);
 248         }
 249
 250         __sync_bool_compare_and_swap(&m->holds_finlock, 1, 0);
 251         if(__sync_bool_compare_and_swap(&m->gcing_for_finlock, 1, 0)) {
 252                 runtime_throw("walkfintab not called from gc");
 253         }
 254 }