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