libbanshee/libcompat/regions.c

   1 /*
   2  * Copyright (c) 1999-2001
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. Neither the name of the University nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  *
  29  */
  30 /* Idea: clear on page alloc rather than individual alloc
  31    Turns out not so good (on lcc at least, seems a wash on mudlle):
  32    logically should be bad for small regions (less than a few pages)
  33 */
  34 #undef PRECLEAR
  35 #undef REGION_PROFILE
  36 #include "regions.h"
  37 #include <assert.h>
  38 #include <stdio.h>
  39 #include <string.h>
  40 #include "radix-tree.h"
  41 #define RPAGESIZE (1 << RPAGELOG)
  42 #define PAGE_GROUP_SIZE 32
  43 #define K 4
  44 #define MAXPAGE (1 << (32 - RPAGELOG))
  45
  46 #define PAGENB(x) ((__rcintptr)(x) >> RPAGELOG)
  47
  48 #define ALIGN(x, n) (((x) + ((n) - 1)) & ~((n) - 1))
  49 #define PALIGN(x, n) ((void *)ALIGN((__rcintptr)(x), n))
  50 #ifdef __GNUC__
  51 #define RALIGNMENT __alignof(double)
  52 #define PTRALIGNMENT __alignof(void *)
  53 #define ALIGNMENT_LONG __alignof(unsigned long)
  54 #else
  55 #define RALIGNMENT 8
  56 #define PTRALIGNMENT 4
  57 #define ALIGNMENT_LONG 4
  58 #endif
  59
  60 typedef unsigned long __rcintptr;
  61
  62 struct ablock {
  63   char *base, *allocfrom;
  64 };
  65
  66 struct allocator {
  67   struct ablock page;
  68   struct ablock superpage;
  69   struct ablock hyperpage;
  70   struct page *pages;
  71   struct page *bigpages;
  72 };
  73
  74 struct Region {
  75   struct allocator normal;
  76   struct Region *parent, *sibling, *children;
  77 };
  78
  79 nomem_handler nomem_h;
  80
  81 /* dummy region for NULL and malloc memory */
  82 struct Region zeroregion;
  83
  84 static void clear(void *start, __rcintptr size)
  85 {
  86   long *clear, *clearend;
  87
  88   clear = (long *)start;
  89   clearend = (long *)((char *)start + size);
  90   do *clear++ = 0;
  91   while (clear < clearend) ;
  92 }
  93
  94 #ifdef PRECLEAR
  95 #define preclear clear
  96 #define postclear(s, e)
  97 #else
  98 #define preclear(s, e)
  99 #define postclear clear
 100 #endif
 101
 102 #include "pages.c"
 103 #include "alloc.c"
 104
 105 static void nochildren(region r)
 106 {
 107   if (r->children)
 108     abort();
 109 }
 110
 111 static void unlink_region(region r)
 112 {
 113   region *scan;
 114
 115   scan = &r->parent->children;
 116   while (*scan != r)
 117     scan = &(*scan)->sibling;
 118   *scan = (*scan)->sibling;
 119 }
 120
 121 static void link_region(region r, region parent)
 122 {
 123   r->sibling = parent->children;
 124   r->parent = parent;
 125   parent->children = r;
 126 }
 127
 128 static int rstart;
 129
 130 void initregion(region r)
 131 {
 132   char *first =
 133     (char *)r - rstart - offsetof(struct page, previous);
 134
 135   /* Start using page with region header as a pointer-containing page */
 136   r->normal.page.base = first;
 137   r->normal.page.allocfrom = (char *)(r + 1);
 138
 139   /* Guarantee failure for all other blocks */
 140   r->normal.superpage.allocfrom = (char *)(K * RPAGESIZE + 1);
 141   r->normal.hyperpage.allocfrom = (char *)(K * K * RPAGESIZE + 1);
 142
 143   /* Remember that r owns this page. */
 144   r->normal.pages = (struct page *)first;
 145   set_region(r->normal.pages, 1, r);
 146 }
 147
 148 region newregion(void)
 149 {
 150   return newsubregion(&zeroregion);
 151 }
 152
 153 region newsubregion(region parent)
 154 {
 155   char *first;
 156   region r;
 157
 158   first = (char *)alloc_single_page(NULL);
 159   preclear(first + offsetof(struct page, pagecount), RPAGESIZE - offsetof(struct page, pagecount));
 160
 161   /* stagger regions across cache lines a bit */
 162   rstart += 64;
 163   if (rstart > RPAGESIZE / K) rstart = 0;
 164   r = (region)(first + rstart + offsetof(struct page, previous));
 165   postclear(r, sizeof *r);
 166   initregion(r);
 167
 168   link_region(r, parent);
 169
 170   return r;
 171 }
 172
 173 void *typed_ralloc(region r, size_t size, type_t t)
 174 {
 175   return rstralloc0(r, size);
 176 }
 177
 178 void *typed_rarrayextend(region r, void *old, size_t n, size_t size, type_t t)
 179 {
 180   return rstrextend0(r, old, n * size);
 181 }
 182
 183 void *typed_rarrayalloc(region r, size_t n, size_t size, type_t t)
 184 {
 185   return typed_ralloc(r, n * size, t);
 186 }
 187
 188 char *rstralloc(region r, size_t size)
 189 {
 190   void *mem, *dummy;
 191
 192   qalloc(r, &r->normal, &dummy, 0, 1, &mem, size, RALIGNMENT, 0);
 193
 194   return mem;
 195 }
 196
 197 char *rstralloc0(region r, size_t size)
 198 {
 199   char *mem;
 200
 201   mem = rstralloc(r, size);
 202   clear(mem, size);
 203
 204   return mem;
 205 }
 206
 207 char *rstrdup(region r, const char *s)
 208 {
 209   char *news = rstralloc(r, strlen(s) + 1);
 210
 211   strcpy(news, s);
 212
 213   return news;
 214 }
 215
 216 static char *internal_rstrextend(region r, const char *old, size_t newsize,
 217                                  int needsclear)
 218 {
 219   /* For now we don't attempt to extend the old storage area */
 220   void *newmem, *hdr;
 221   unsigned long *oldhdr, oldsize;
 222
 223   qalloc(r, &r->normal, &hdr, sizeof(unsigned long), ALIGNMENT_LONG,
 224          &newmem, newsize, RALIGNMENT, 0);
 225
 226   /* If we don't do this we can't find the header: */
 227   hdr = (char *)newmem - sizeof(unsigned long);
 228
 229   *(unsigned long *)hdr = newsize;
 230
 231   if (old)
 232     {
 233       oldhdr = (unsigned long *)(old - ALIGNMENT_LONG);
 234       oldsize = *oldhdr;
 235
 236       if (oldsize > newsize)
 237         oldsize = newsize;
 238       else if (needsclear)
 239         clear((char *) newmem + oldsize, newsize - oldsize);
 240       memcpy(newmem, old, oldsize);
 241     }
 242   else if (needsclear)
 243     clear(newmem, newsize);
 244
 245   return newmem;
 246 }
 247
 248 char *rstrextend(region r, const char *old, size_t newsize)
 249 {
 250   return internal_rstrextend(r, old, newsize, 0);
 251 }
 252
 253 char *rstrextend0(region r, const char *old, size_t newsize)
 254 {
 255   return internal_rstrextend(r, old, newsize, 1);
 256 }
 257
 258 void typed_rarraycopy(void *to, void *from, size_t n, size_t size, type_t type)
 259 {
 260   memcpy(to, from, n * size);
 261 }
 262
 263 static void delregion(region r)
 264 {
 265   nochildren(r);
 266   free_all_pages(r, &r->normal);
 267 }
 268
 269 void deleteregion(region r)
 270 {
 271   unlink_region(r);
 272   delregion(r);
 273 }
 274
 275 void deleteregion_ptr(region *r)
 276 {
 277   region tmp = *r;
 278
 279   *r = NULL;
 280   deleteregion(tmp);
 281 }
 282
 283 void deleteregion_array(int n, region *regions)
 284 {
 285   int i;
 286
 287   for (i = 0; i < n; i++)
 288     unlink_region(regions[i]);
 289
 290   for (i = 0; i < n; i++)
 291     {
 292       delregion(regions[i]);
 293       regions[i] = NULL;
 294     }
 295 }
 296
 297 region regionof(void *ptr)
 298 {
 299   return radix_tree_lookup (&__rcregionmap, (unsigned long)ptr >> RPAGELOG);
 300 }
 301
 302 void region_init(void)
 303 {
 304   static int initialized = 0;
 305   radix_tree_init ();
 306   if ( initialized )
 307     return;
 308   else
 309     {
 310       rstart = -64; /* Save 64 bytes of memory! (sometimes ;-)) */
 311       init_pages();
 312     }
 313
 314   initialized = 1;
 315 }
 316
 317 nomem_handler set_nomem_handler(nomem_handler newhandler)
 318 {
 319   nomem_handler oldh = nomem_h;
 320
 321   nomem_h = newhandler;
 322
 323   return oldh;
 324 }
 325
 326 /*
 327 int region_main(int argc, char **argv, char **envp);
 328
 329 int main(int argc, char **argv, char **envp)
 330 {
 331   region_init();
 332   return region_main(argc, argv, envp);
 333 }
 334 */
 335
 336
 337 /* Debugging support */
 338
 339 static FILE *out;
 340
 341 static void printref(void *x)
 342 {
 343 /*  if (x >= (void *)__rcregionmap && x < (void *)&__rcregionmap[MAXPAGE])
 344     return;
 345 */
 346 #ifdef RCPAIRS
 347   if (x >= (void *)__rcregions && x < (void *)&__rcregions[MAXREGIONS])
 348     return;
 349
 350 #endif
 351
 352   fprintf(out, "info symbol 0x%p\n", x);
 353 }
 354
 355 void findrefs(region r, void *from, void *to)
 356 {
 357   char *f;
 358
 359   if (!out)
 360     out = fopen("/dev/tty", "w");
 361
 362   for (f = PALIGN(from, PTRALIGNMENT); f < (char *)to; f += PTRALIGNMENT)
 363     if (regionof(*(void **)f) == r)
 364       printref(f);
 365
 366   fflush(out);
 367 }
 368
 369 #ifdef sparc
 370 extern void _DYNAMIC, _end;
 371
 372 void findgrefs(region r)
 373 {
 374   findrefs(r, &_DYNAMIC, &_end);
 375 }
 376 #endif
 377
 378 void findrrefs(region r, region from)
 379 {
 380   struct page *p;
 381
 382   for (p = from->normal.pages; p; p = p->next)
 383     findrefs(r, (char *)&p->previous, (char *)p + RPAGESIZE);
 384
 385   for (p = r->normal.bigpages; p; p = p->next)
 386     findrefs(r, (char *)&p->previous, (char *)p + p->pagecount * RPAGESIZE);
 387 }