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 static void
  45 addfintab(Fintab *t, void *k, void (*fn)(void*), const struct __go_func_type *ft)
  46 {
  47         int32 i, j;
  48
  49         i = (uintptr)k % (uintptr)t->max;
  50         for(j=0; j<t->max; j++) {
  51                 if(t->fkey[i] == nil) {
  52                         t->nkey++;
  53                         goto ret;
  54                 }
  55                 if(t->fkey[i] == (void*)-1) {
  56                         t->ndead--;
  57                         goto ret;
  58                 }
  59                 if(++i == t->max)
  60                         i = 0;
  61         }
  62
  63         // cannot happen - table is known to be non-full
  64         runtime_throw("finalizer table inconsistent");
  65
  66 ret:
  67         t->fkey[i] = k;
  68         t->val[i].fn = fn;
  69         t->val[i].ft = ft;
  70 }
  71
  72 static bool
  73 lookfintab(Fintab *t, void *k, bool del, Fin *f)
  74 {
  75         int32 i, j;
  76
  77         if(t->max == 0)
  78                 return false;
  79         i = (uintptr)k % (uintptr)t->max;
  80         for(j=0; j<t->max; j++) {
  81                 if(t->fkey[i] == nil)
  82                         return false;
  83                 if(t->fkey[i] == k) {
  84                         if(f)
  85                                 *f = t->val[i];
  86                         if(del) {
  87                                 t->fkey[i] = (void*)-1;
  88                                 t->val[i].fn = nil;
  89                                 t->val[i].ft = nil;
  90                                 t->ndead++;
  91                         }
  92                         return true;
  93                 }
  94                 if(++i == t->max)
  95                         i = 0;
  96         }
  97
  98         // cannot happen - table is known to be non-full
  99         runtime_throw("finalizer table inconsistent");
 100         return false;
 101 }
 102
 103 static void
 104 resizefintab(Fintab *tab)
 105 {
 106         Fintab newtab;
 107         void *k;
 108         int32 i;
 109
 110         runtime_memclr((byte*)&newtab, sizeof newtab);
 111         newtab.max = tab->max;
 112         if(newtab.max == 0)
 113                 newtab.max = 3*3*3;
 114         else if(tab->ndead < tab->nkey/2) {
 115                 // grow table if not many dead values.
 116                 // otherwise just rehash into table of same size.
 117                 newtab.max *= 3;
 118         }
 119
 120         newtab.fkey = runtime_mallocgc(newtab.max*sizeof newtab.fkey[0], FlagNoPointers, 0, 1);
 121         newtab.val = runtime_mallocgc(newtab.max*sizeof newtab.val[0], 0, 0, 1);
 122
 123         for(i=0; i<tab->max; i++) {
 124                 k = tab->fkey[i];
 125                 if(k != nil && k != (void*)-1)
 126                         addfintab(&newtab, k, tab->val[i].fn, tab->val[i].ft);
 127         }
 128
 129         runtime_free(tab->fkey);
 130         runtime_free(tab->val);
 131
 132         tab->fkey = newtab.fkey;
 133         tab->val = newtab.val;
 134         tab->nkey = newtab.nkey;
 135         tab->ndead = newtab.ndead;
 136         tab->max = newtab.max;
 137 }
 138
 139 bool
 140 runtime_addfinalizer(void *p, void (*f)(void*), const struct __go_func_type *ft)
 141 {
 142         Fintab *tab;
 143         byte *base;
 144
 145         if(debug) {
 146                 if(!runtime_mlookup(p, &base, nil, nil) || p != base)
 147                         runtime_throw("addfinalizer on invalid pointer");
 148         }
 149
 150         tab = TAB(p);
 151         runtime_lock(tab);
 152         if(f == nil) {
 153                 if(lookfintab(tab, p, true, nil))
 154                         runtime_setblockspecial(p, false);
 155                 runtime_unlock(tab);
 156                 return true;
 157         }
 158
 159         if(lookfintab(tab, p, false, nil)) {
 160                 runtime_unlock(tab);
 161                 return false;
 162         }
 163
 164         if(tab->nkey >= tab->max/2+tab->max/4) {
 165                 // keep table at most 3/4 full:
 166                 // allocate new table and rehash.
 167                 resizefintab(tab);
 168         }
 169
 170         addfintab(tab, p, f, ft);
 171         runtime_setblockspecial(p, true);
 172         runtime_unlock(tab);
 173         return true;
 174 }
 175
 176 // get finalizer; if del, delete finalizer.
 177 // caller is responsible for updating RefHasFinalizer (special) bit.
 178 bool
 179 runtime_getfinalizer(void *p, bool del, void (**fn)(void*), const struct __go_func_type **ft)
 180 {
 181         Fintab *tab;
 182         bool res;
 183         Fin f;
 184
 185         tab = TAB(p);
 186         runtime_lock(tab);
 187         res = lookfintab(tab, p, del, &f);
 188         runtime_unlock(tab);
 189         if(res==false)
 190                 return false;
 191         *fn = f.fn;
 192         *ft = f.ft;
 193         return true;
 194 }
 195
 196 void
 197 runtime_walkfintab(void (*fn)(void*), void (*scan)(byte *, int64))
 198 {
 199         void **key;
 200         void **ekey;
 201         int32 i;
 202
 203         for(i=0; i<TABSZ; i++) {
 204                 runtime_lock(&fintab[i]);
 205                 key = fintab[i].fkey;
 206                 ekey = key + fintab[i].max;
 207                 for(; key < ekey; key++)
 208                         if(*key != nil && *key != ((void*)-1))
 209                                 fn(*key);
 210                 scan((byte*)&fintab[i].fkey, sizeof(void*));
 211                 scan((byte*)&fintab[i].val, sizeof(void*));
 212                 runtime_unlock(&fintab[i]);
 213         }
 214 }