system/kernel/ke/bsdmalloc.c

   1 /*
   2  * ----------------------------------------------------------------------------
   3  * "THE BEER-WARE LICENSE" (Revision 42):
   4  * <phk@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
   5  * can do whatever you want with this stuff. If we meet some day, and you think
   6  * this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
   7  * ----------------------------------------------------------------------------
   8  */
   9
  10 #include <stdint.h>
  11 #include "mm/memory.h"
  12 #include "ke/debug.h"
  13
  14 static int printf(const char *fmt, ...)
  15 {
  16     int *args = (int*)&fmt + 1;
  17     kePrintList(fmt, &args);
  18     return 0;
  19 }
  20
  21 /*
  22  * Defining MALLOC_EXTRA_SANITY will enable extra checks which are related
  23  * to internal conditions and consistency in malloc.c. This has a
  24  * noticeable runtime performance hit, and generally will not do you
  25  * any good unless you fiddle with the internals of malloc or want
  26  * to catch random pointer corruption as early as possible.
  27  */
  28 #ifndef MALLOC_EXTRA_SANITY
  29 #define MALLOC_EXTRA_SANITY
  30 #endif
  31
  32 /*
  33  * What to use for Junk.  This is the byte value we use to fill with
  34  * when the 'J' option is enabled.
  35  */
  36 #define SOME_JUNK   0xd0        /* as in "Duh" :-) */
  37 #define SOME_FREE_JUNK   0xf0
  38
  39 /*
  40  * The basic parameters you can tweak.
  41  *
  42  * malloc_minsize   minimum size of an allocation in bytes.
  43  *          If this is too small it's too much work
  44  *          to manage them.  This is also the smallest
  45  *          unit of alignment used for the storage
  46  *          returned by malloc/realloc.
  47  *
  48  */
  49
  50 /* Insert your combination here... */
  51
  52 /*#if defined(__FOOCPU__) && defined(__BAROS__)
  53 #   define malloc_minsize       16U
  54 #endif*/ /* __FOOCPU__ && __BAROS__ */
  55
  56 #include "bsdtypes.h"
  57 #include "string.h"
  58
  59 void* mem_allocate(uint32_t size, uint32_t flags)
  60 {
  61     uintptr_t vaddr = mmFindFreeKernelPages(MM_MAX_KERNEL_PAGE,
  62                 MM_MIN_KERNEL_PAGE, 0, (size + 0xFFF) & ~0xFFF);
  63         if (!vaddr) return 0;
  64         uint32_t i;
  65         for (i = 0; i < (size + 0xFFF) / 0x1000; i++)
  66         {
  67         uintptr_t paddr = mmAllocPhysicalMemory(0, 0, 0x1000);
  68         if (!paddr) return 0;
  69             mmMapKernelMemory(paddr, vaddr + i * 0x1000, MM_MAP_READ | MM_MAP_WRITE);
  70         }
  71     return (void*)vaddr;
  72 }
  73 void mem_free(void *addr, uint32_t size)
  74 {
  75         uint32_t i;
  76         for (i = 0; i < (size + 0xFFF) / 0x1000; i++)
  77         {
  78             uintptr_t vaddr = (uintptr_t)addr + i * 0x1000;
  79             uintptr_t paddr = mmKernelGetPhysAddress(vaddr);
  80             if (paddr != 0)
  81             mmFreePhysicalMemory(paddr, 0x1000);
  82         mmMapKernelMemory(paddr, vaddr, MM_MAP_READ | MM_MAP_WRITE);
  83         }
  84 }
  85
  86 extern int errno;
  87 #define ENOMEM 1337
  88 #define MAP_FAILED NULL
  89 #define LOST_MALLOC_PAGESIZE 4096
  90
  91 /*
  92  * No user serviceable parts behind this point.
  93  */
  94
  95 /*
  96  * This structure describes a page worth of chunks.
  97  */
  98
  99 struct pginfo {
 100     struct pginfo   *next;  /* next on the free list */
 101     void        *page;  /* Pointer to the page */
 102     u_short     size;   /* size of this page's chunks */
 103     u_short     shift;  /* How far to shift for this size chunks */
 104     u_short     free;   /* How many free chunks */
 105     u_short     total;  /* How many chunk */
 106     u_int       bits[1]; /* Which chunks are free */
 107 };
 108
 109 /*
 110  * This structure describes a number of free pages.
 111  */
 112
 113 struct pgfree {
 114     struct pgfree   *next;  /* next run of free pages */
 115     struct pgfree   *prev;  /* prev run of free pages */
 116     void        *page;  /* pointer to free pages */
 117     void        *end;   /* pointer to end of free pages */
 118     size_t      size;   /* number of bytes free */
 119 };
 120
 121 /*
 122  * How many bits per u_int in the bitmap.
 123  * Change only if not 8 bits/byte
 124  */
 125 #define MALLOC_BITS ((int)(8*sizeof(u_int)))
 126
 127 /*
 128  * Magic values to put in the page_directory
 129  */
 130 #define MALLOC_NOT_MINE ((struct pginfo*) 0)
 131 #define MALLOC_FREE     ((struct pginfo*) 1)
 132 #define MALLOC_FIRST    ((struct pginfo*) 2)
 133 #define MALLOC_FOLLOW   ((struct pginfo*) 3)
 134 #define MALLOC_MAGIC    ((struct pginfo*) 4)
 135
 136 /*
 137  * Page size related parameters, computed at run-time.
 138  */
 139 static size_t malloc_pagesize;
 140 static size_t malloc_pageshift;
 141 static size_t malloc_pagemask;
 142
 143 #ifndef malloc_minsize
 144 #define malloc_minsize          16U
 145 #endif
 146
 147 #ifndef malloc_maxsize
 148 #define malloc_maxsize          ((malloc_pagesize)>>1)
 149 #endif
 150
 151 #define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask)))
 152 #define ptr2idx(foo) \
 153     (((size_t)(uintptr_t)(foo) >> malloc_pageshift)-malloc_origo)
 154
 155 #ifndef THREAD_LOCK
 156 #define THREAD_LOCK()
 157 #endif
 158
 159 #ifndef THREAD_UNLOCK
 160 #define THREAD_UNLOCK()
 161 #endif
 162
 163 #ifndef MMAP_FD
 164 #define MMAP_FD (-1)
 165 #endif
 166
 167 #ifndef INIT_MMAP
 168 #define INIT_MMAP()
 169 #endif
 170
 171 #ifndef MADV_FREE
 172 #define MADV_FREE MADV_DONTNEED
 173 #endif
 174
 175 /* Set when initialization has been done */
 176 static unsigned malloc_started = 0;
 177
 178 /* Recusion flag for public interface. */
 179 static int malloc_active = 0;
 180
 181 /* Number of free pages we cache */
 182 static unsigned malloc_cache = 16;
 183
 184 /* The offset from pagenumber to index into the page directory */
 185 static size_t malloc_origo;
 186
 187 /* The last index in the page directory we care about */
 188 static size_t last_idx;
 189
 190 /* Pointer to page directory. Allocated "as if with" malloc */
 191 static struct   pginfo **page_dir;
 192
 193 /* How many slots in the page directory */
 194 static unsigned malloc_ninfo;
 195
 196 /* Free pages line up here */
 197 static struct pgfree free_list;
 198
 199 /* Abort(), user doesn't handle problems.  */
 200 static int malloc_abort;
 201
 202 /* Are we trying to die ?  */
 203 static int suicide;
 204
 205 /* always realloc ?  */
 206 static int malloc_realloc;
 207
 208 /* pass the kernel a hint on free pages ?  */
 209 static int malloc_hint = 0;
 210
 211 /* xmalloc behaviour ?  */
 212 static int malloc_xmalloc;
 213
 214 /* sysv behaviour for malloc(0) ?  */
 215 static int malloc_sysv;
 216
 217 /* zero fill ?  */
 218 static int malloc_zero;
 219
 220 /* junk fill ?  */
 221 static int malloc_junk;
 222
 223 #ifdef HAS_UTRACE
 224
 225 /* utrace ?  */
 226 static int malloc_utrace;
 227
 228 struct ut { void *p; size_t s; void *r; };
 229
 230 #define UTRACE(a, b, c) \
 231     if (malloc_utrace) {            \
 232         struct ut u;            \
 233         u.p=a; u.s = b; u.r=c;      \
 234         utrace(UTRACE_LABEL (void *) &u, sizeof u); \
 235     }
 236 #else /* !HAS_UTRACE */
 237 #define UTRACE(a,b,c)
 238 #endif /* HAS_UTRACE */
 239
 240 /* my last break. */
 241 static void *malloc_brk;
 242
 243 /* one location cache for free-list holders */
 244 static struct pgfree *px;
 245
 246 /* compile-time options */
 247 static char *malloc_options = "";
 248
 249 /* Name of the current public function */
 250 static const char *malloc_func;
 251
 252 /* Macro for mmap */
 253 #define MMAP(size) \
 254     memset(mem_allocate(size, 0), 0, size)
 255
 256 /*#define sbrk(size) \
 257     mem_allocate(size, 0)*/
 258
 259 #define munmap(start, size) mem_free(start, size)
 260
 261 /*    mmap(0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
 262         MMAP_FD, (off_t)0);*/
 263
 264 /*
 265 static int brk(void* end_data_segment) {
 266     return -1;
 267 }
 268 */
 269
 270 void init_memory_manager() {}
 271
 272
 273 /*
 274  * Necessary function declarations
 275  */
 276 static int extend_pgdir(size_t idx);
 277 static void *imalloc(size_t size);
 278 static void ifree(void *ptr);
 279 static void *irealloc(void *ptr, size_t size);
 280
 281 static void
 282 wrterror(const char *p)
 283 {
 284 //    const char *progname = getprogname();
 285     const char *q = " error: ";
 286
 287 //    printf("%s", progname);
 288     printf("%s", malloc_func);
 289     printf("%s", q);
 290     printf("%s", p);
 291
 292     suicide = 1;
 293     while(1);
 294 }
 295
 296 static void
 297 wrtwarning(const char *p)
 298 {
 299     /*
 300     const char *progname = getprogname();
 301     const char *q = " warning: ";
 302 */
 303     if (malloc_abort)
 304     wrterror(p);
 305     /*
 306     write(STDERR_FILENO, progname, strlen(progname));
 307     write(STDERR_FILENO, malloc_func, strlen(malloc_func));
 308     write(STDERR_FILENO, q, strlen(q));
 309     write(STDERR_FILENO, p, strlen(p));
 310     */
 311 }
 312
 313 /*
 314  * Allocate a number of pages from the OS
 315  */
 316 static void *
 317 map_pages(size_t pages)
 318 {
 319     caddr_t rresult, tail;
 320
 321     rresult = mem_allocate(pages << malloc_pageshift, 0);
 322     if (rresult == NULL) {
 323         errno = ENOMEM;
 324     }
 325
 326     intptr_t bytes = pages << malloc_pageshift;
 327
 328     tail = rresult + (size_t)bytes;
 329     last_idx = ptr2idx(tail) - 1;
 330     malloc_brk = tail;
 331
 332     //printf("[origo = %x, tail = %x, last_idx = %x, rresult = %x]", malloc_origo, tail, last_idx, rresult);
 333
 334     if ((last_idx+1) >= malloc_ninfo && !extend_pgdir(last_idx)) {
 335
 336         malloc_brk = rresult;
 337         last_idx = ptr2idx(malloc_brk) - 1;
 338
 339         /* FIXME: Put back break point since we failed. */
 340         /*if (brk(malloc_brk)) {
 341             wrterror("[b] brk(2) failed [internal error]\n");
 342         }*/
 343         errno = ENOMEM;
 344         return 0;
 345     }
 346
 347
 348     return rresult;
 349
 350 #if 0
 351     caddr_t result, rresult, tail;
 352     intptr_t bytes = pages << malloc_pageshift;
 353
 354     if (bytes < 0 || (size_t)bytes < pages) {
 355     errno = ENOMEM;
 356     return NULL;
 357     }
 358
 359     if ((result = sbrk(bytes)) == (void *)-1)
 360     return NULL;
 361
 362     /*
 363      * Round to a page, in case sbrk(2) did not do this for us
 364      */
 365     rresult = (caddr_t)pageround((size_t)(uintptr_t)result);
 366     if (result < rresult) {
 367     /* make sure we have enough space to fit bytes */
 368     if (sbrk((intptr_t)(rresult - result)) == (void *) -1) {
 369         /* we failed, put everything back */
 370         // FIXME Speicher wirklich zurückgeben
 371 /*        if (brk(result)) {
 372         wrterror("brk(2) failed [internal error]\n");
 373         }*/
 374     }
 375     }
 376     tail = rresult + (size_t)bytes;
 377
 378     last_idx = ptr2idx(tail) - 1;
 379     malloc_brk = tail;
 380
 381     if ((last_idx+1) >= malloc_ninfo && !extend_pgdir(last_idx)) {
 382     malloc_brk = result;
 383     last_idx = ptr2idx(malloc_brk) - 1;
 384     /* Put back break point since we failed. */
 385     if (brk(malloc_brk))
 386         wrterror("[b] brk(2) failed [internal error]\n");
 387     return 0;
 388     }
 389
 390     return rresult;
 391 #endif
 392 }
 393
 394 /*
 395  * Extend page directory
 396  */
 397 static int
 398 extend_pgdir(size_t idx)
 399 {
 400     struct  pginfo **new, **old;
 401     size_t newlen, oldlen;
 402
 403     printf("extend_pgdir %x", idx);
 404
 405     /* check for overflow */
 406     if (
 407         (
 408             (
 409                 (
 410                     ~(1UL <<
 411                         ((sizeof(size_t) * NBBY) - 1)
 412                     )
 413                     / sizeof(*page_dir)
 414                 ) + 1
 415             )
 416             +
 417             (
 418                 malloc_pagesize / sizeof *page_dir
 419             )
 420         ) < idx
 421     ) {
 422     errno = ENOMEM;
 423     return 0;
 424     }
 425
 426     //printf("++");
 427
 428     /* Make it this many pages */
 429     newlen = pageround(idx * sizeof *page_dir) + malloc_pagesize;
 430
 431     /* remember the old mapping size */
 432     oldlen = malloc_ninfo * sizeof *page_dir;
 433
 434     /*
 435      * NOTE: we allocate new pages and copy the directory rather than tempt
 436      * fate by trying to "grow" the region.. There is nothing to prevent
 437      * us from accidentally re-mapping space that's been allocated by our caller
 438      * via dlopen() or other mmap().
 439      *
 440      * The copy problem is not too bad, as there is 4K of page index per
 441      * 4MB of malloc arena.
 442      *
 443      * We can totally avoid the copy if we open a file descriptor to associate
 444      * the anon mappings with.  Then, when we remap the pages at the new
 445      * address, the old pages will be "magically" remapped..  But this means
 446      * keeping open a "secret" file descriptor.....
 447      */
 448
 449     /* Get new pages */
 450     new = (struct pginfo**) MMAP(newlen);
 451     if (new == MAP_FAILED)
 452     return 0;
 453
 454     //printf("**");
 455
 456     /* Copy the old stuff */
 457     memcpy(new, page_dir, oldlen);
 458
 459     //printf("--");
 460
 461     /* register the new size */
 462     malloc_ninfo = newlen / sizeof *page_dir;
 463
 464     /* swap the pointers */
 465     old = page_dir;
 466     page_dir = new;
 467
 468     /* Now free the old stuff */
 469     munmap(old, oldlen);
 470     //printf("//");
 471
 472     return 1;
 473 }
 474
 475 /*
 476  * Initialize the world
 477  */
 478 static void
 479 malloc_init (void)
 480 {
 481     char *p, b[64];
 482     int i, j;
 483     int errnosave;
 484
 485     /*
 486      * Compute page-size related variables.
 487      */
 488     malloc_pagesize = LOST_MALLOC_PAGESIZE;
 489     malloc_pagemask = malloc_pagesize - 1;
 490     for (malloc_pageshift = 0;
 491      (1UL << malloc_pageshift) != malloc_pagesize;
 492      malloc_pageshift++)
 493     /* nothing */ ;
 494
 495     INIT_MMAP();
 496
 497 #ifdef MALLOC_EXTRA_SANITY
 498     malloc_junk = 1;
 499 #endif /* MALLOC_EXTRA_SANITY */
 500
 501     for (i = 0; i < 3; i++) {
 502     if (i == 0) {
 503         errnosave = errno;
 504         j = 0; //readlink("/etc/malloc.conf", b, sizeof b - 1);
 505         errno = errnosave;
 506         if (j <= 0)
 507         continue;
 508         b[j] = '\0';
 509         p = b;
 510     } /*else if (i == 1) {
 511         p = getenv("MALLOC_OPTIONS");
 512     }*/ else {
 513         p = malloc_options;
 514     }
 515     for (; p != NULL && *p != '\0'; p++) {
 516         switch (*p) {
 517         case '>': malloc_cache   <<= 1; break;
 518         case '<': malloc_cache   >>= 1; break;
 519         case 'a': malloc_abort   = 0; break;
 520         case 'A': malloc_abort   = 1; break;
 521         case 'h': malloc_hint    = 0; break;
 522         case 'H': malloc_hint    = 1; break;
 523         case 'r': malloc_realloc = 0; break;
 524         case 'R': malloc_realloc = 1; break;
 525         case 'j': malloc_junk    = 0; break;
 526         case 'J': malloc_junk    = 1; break;
 527 #ifdef HAS_UTRACE
 528         case 'u': malloc_utrace  = 0; break;
 529         case 'U': malloc_utrace  = 1; break;
 530 #endif
 531         case 'v': malloc_sysv    = 0; break;
 532         case 'V': malloc_sysv    = 1; break;
 533         case 'x': malloc_xmalloc = 0; break;
 534         case 'X': malloc_xmalloc = 1; break;
 535         case 'z': malloc_zero    = 0; break;
 536         case 'Z': malloc_zero    = 1; break;
 537         default:
 538             j = malloc_abort;
 539             malloc_abort = 0;
 540             wrtwarning("unknown char in MALLOC_OPTIONS.\n");
 541             malloc_abort = j;
 542             break;
 543         }
 544     }
 545     }
 546
 547     UTRACE(0, 0, 0);
 548
 549     /*
 550      * We want junk in the entire allocation, and zero only in the part
 551      * the user asked for.
 552      */
 553     if (malloc_zero)
 554     malloc_junk=1;
 555
 556     /*
 557      * If we run with junk (or implicitly from above: zero), we want to
 558      * force realloc() to get new storage, so we can DTRT with it.
 559      */
 560     if (malloc_junk)
 561     malloc_realloc=1;
 562
 563     /* Allocate one page for the page directory */
 564     page_dir = (struct pginfo **) MMAP(malloc_pagesize);
 565
 566     if (page_dir == MAP_FAILED)
 567     wrterror("mmap(2) failed, check limits.\n");
 568
 569     /*
 570      * We need a maximum of malloc_pageshift buckets, steal these from the
 571      * front of the page_directory;
 572      */
 573     //malloc_origo = malloc_pageshift;
 574     malloc_origo = ((uint32_t) page_dir >> malloc_pageshift) - malloc_pageshift;
 575
 576     /*
 577     pageround((size_t)(uintptr_t)sbrk((intptr_t)0))
 578     >> malloc_pageshift;
 579     malloc_origo -= malloc_pageshift;
 580     */
 581
 582     malloc_ninfo = malloc_pagesize / sizeof *page_dir;
 583
 584     /* Recalculate the cache size in bytes, and make sure it's nonzero */
 585
 586     if (!malloc_cache)
 587     malloc_cache++;
 588
 589     malloc_cache <<= malloc_pageshift;
 590
 591     /*
 592      * This is a nice hack from Kaleb Keithly (kaleb@x.org).
 593      * We can sbrk(2) further back when we keep this on a low address.
 594      */
 595     px = (struct pgfree *) imalloc (sizeof *px);
 596
 597     /* Been here, done that */
 598     malloc_started++;
 599 }
 600
 601 /*
 602  * Allocate a number of complete pages
 603  */
 604 static void *
 605 malloc_pages(size_t size)
 606 {
 607     void *p, *delay_free = NULL;
 608     size_t i;
 609     struct pgfree *pf;
 610     size_t idx;
 611
 612     //printf("malloc_pages(%d)\n", size);
 613
 614     idx = pageround(size);
 615     if (idx < size) {
 616     errno = ENOMEM;
 617     return NULL;
 618     } else
 619     size = idx;
 620
 621     p = NULL;
 622
 623     /* Look for free pages before asking for more */
 624     for(pf = free_list.next; pf; pf = pf->next) {
 625
 626 #ifdef MALLOC_EXTRA_SANITY
 627     if (pf->size & malloc_pagemask)
 628         wrterror("(ES): junk length entry on free_list.\n");
 629     if (!pf->size)
 630         wrterror("(ES): zero length entry on free_list.\n");
 631     if (pf->page == pf->end)
 632         wrterror("(ES): zero entry on free_list.\n");
 633     if (pf->page > pf->end)
 634         wrterror("(ES): sick entry on free_list.\n");
 635 /*    if ((void*)pf->page >= (void*)sbrk(0))
 636         wrterror("(ES): entry on free_list past brk.\n");*/
 637     if (page_dir[ptr2idx(pf->page)] != MALLOC_FREE)
 638         wrterror("(ES): non-free first page on free-list.\n");
 639     if (page_dir[ptr2idx(pf->end)-1] != MALLOC_FREE)
 640         wrterror("(ES): non-free last page on free-list.\n");
 641 #endif /* MALLOC_EXTRA_SANITY */
 642
 643     if (pf->size < size)
 644         continue;
 645
 646     if (pf->size == size) {
 647         p = pf->page;
 648         if (pf->next != NULL)
 649             pf->next->prev = pf->prev;
 650         pf->prev->next = pf->next;
 651         delay_free = pf;
 652         break;
 653     }
 654
 655     p = pf->page;
 656     pf->page = (char *)pf->page + size;
 657     pf->size -= size;
 658     break;
 659     }
 660
 661 #ifdef MALLOC_EXTRA_SANITY
 662     if (p != NULL && page_dir[ptr2idx(p)] != MALLOC_FREE)
 663     wrterror("(ES): allocated non-free page on free-list.\n");
 664 #endif /* MALLOC_EXTRA_SANITY */
 665
 666     size >>= malloc_pageshift;
 667
 668     /* Map new pages */
 669     if (p == NULL)
 670     p = map_pages(size);
 671
 672     if (p != NULL) {
 673
 674     idx = ptr2idx(p);
 675     page_dir[idx] = MALLOC_FIRST;
 676     for (i=1;i<size;i++)
 677         page_dir[idx+i] = MALLOC_FOLLOW;
 678
 679     if (malloc_junk)
 680         memset(p, SOME_JUNK, size << malloc_pageshift);
 681     }
 682
 683     if (delay_free) {
 684     if (px == NULL)
 685         px = delay_free;
 686     else
 687         ifree(delay_free);
 688     }
 689
 690     return p;
 691 }
 692
 693 /*
 694  * Allocate a page of fragments
 695  */
 696
 697 static inline int
 698 malloc_make_chunks(int bits)
 699 {
 700     struct  pginfo *bp;
 701     void *pp;
 702     int i, k, l;
 703
 704     /* Allocate a new bucket */
 705     pp = malloc_pages(malloc_pagesize);
 706     if (pp == NULL)
 707     return 0;
 708
 709     /* Find length of admin structure */
 710     l = (int)offsetof(struct pginfo, bits[0]);
 711     l += sizeof bp->bits[0] *
 712     (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
 713
 714     /* Don't waste more than two chunks on this */
 715     if ((1<<(bits)) <= l+l) {
 716     bp = (struct  pginfo *)pp;
 717     } else {
 718     bp = (struct  pginfo *)imalloc((size_t)l);
 719     if (bp == NULL) {
 720         ifree(pp);
 721         return 0;
 722     }
 723     }
 724
 725     bp->size = (1<<bits);
 726     bp->shift = bits;
 727     bp->total = bp->free = malloc_pagesize >> bits;
 728     bp->page = pp;
 729
 730     /* set all valid bits in the bitmap */
 731     k = bp->total;
 732     i = 0;
 733
 734     /* Do a bunch at a time */
 735     for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
 736     bp->bits[i / MALLOC_BITS] = ~0U;
 737
 738     for(; i < k; i++)
 739         bp->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS);
 740
 741     if (bp == bp->page) {
 742     /* Mark the ones we stole for ourselves */
 743     for(i=0;l > 0;i++) {
 744         bp->bits[i/MALLOC_BITS] &= ~(1<<(i%MALLOC_BITS));
 745         bp->free--;
 746         bp->total--;
 747         l -= (1 << bits);
 748     }
 749     }
 750
 751     /* MALLOC_LOCK */
 752
 753     page_dir[ptr2idx(pp)] = bp;
 754
 755     bp->next = page_dir[bits];
 756     page_dir[bits] = bp;
 757
 758     /* MALLOC_UNLOCK */
 759
 760     return 1;
 761 }
 762
 763 /*
 764  * Allocate a fragment
 765  */
 766 static void *
 767 malloc_bytes(size_t size)
 768 {
 769     size_t i;
 770     int j;
 771     u_int u;
 772     struct  pginfo *bp;
 773     int k;
 774     u_int *lp;
 775
 776     //printf("malloc_bytes(%d)\n", size);
 777
 778     /* Don't bother with anything less than this */
 779     if (size < malloc_minsize)
 780         size = malloc_minsize;
 781
 782     /* Find the right bucket */
 783     j = 1;
 784     i = size-1;
 785     while (i >>= 1)
 786         j++;
 787
 788     /* If it's empty, make a page more of that size chunks */
 789     if (page_dir[j] == NULL && !malloc_make_chunks(j))
 790         return NULL;
 791
 792     bp = page_dir[j];
 793
 794     /* Find first word of bitmap which isn't empty */
 795     for (lp = bp->bits; !*lp; lp++)
 796         ;
 797
 798     /* Find that bit, and tweak it */
 799     u = 1;
 800     k = 0;
 801     while (!(*lp & u)) {
 802         u += u;
 803         k++;
 804     }
 805     *lp ^= u;
 806
 807     /* If there are no more free, remove from free-list */
 808     if (!--bp->free) {
 809         page_dir[j] = bp->next;
 810         bp->next = NULL;
 811     }
 812
 813     /* Adjust to the real offset of that chunk */
 814     k += (lp-bp->bits)*MALLOC_BITS;
 815     k <<= bp->shift;
 816
 817     if (malloc_junk)
 818         memset((u_char*)bp->page + k, SOME_JUNK, (size_t)bp->size);
 819
 820     return (u_char *)bp->page + k;
 821 }
 822
 823 /*
 824  * Allocate a piece of memory
 825  */
 826 static void *
 827 imalloc(size_t size)
 828 {
 829     void *result;
 830
 831     if (suicide)
 832         while(1);
 833
 834     if ((size + malloc_pagesize) < size)    /* Check for overflow */
 835         result = NULL;
 836     else if (size <= malloc_maxsize)
 837         result = malloc_bytes(size);
 838     else
 839         result = malloc_pages(size);
 840
 841     if (malloc_abort && result == NULL)
 842         wrterror("allocation failed.\n");
 843
 844     if (malloc_zero && result != NULL)
 845         memset(result, 0, size);
 846
 847     return result;
 848 }
 849
 850 /*
 851  * Change the size of an allocation.
 852  */
 853 static void *
 854 irealloc(void *ptr, size_t size)
 855 {
 856     void *p;
 857     size_t osize, idx;
 858     struct pginfo **mp;
 859     size_t i;
 860
 861     if (suicide)
 862         while(1);
 863
 864     idx = ptr2idx(ptr);
 865
 866     if (idx < malloc_pageshift) {
 867     wrtwarning("junk pointer, too low to make sense.\n");
 868     return 0;
 869     }
 870
 871     if (idx > last_idx) {
 872     wrtwarning("junk pointer, too high to make sense.\n");
 873     return 0;
 874     }
 875
 876     mp = &page_dir[idx];
 877
 878     if (*mp == MALLOC_FIRST) {          /* Page allocation */
 879
 880     /* Check the pointer */
 881     if ((size_t)(uintptr_t)ptr & malloc_pagemask) {
 882         wrtwarning("modified (page-) pointer.\n");
 883         return NULL;
 884     }
 885
 886     /* Find the size in bytes */
 887     for (osize = malloc_pagesize; *++mp == MALLOC_FOLLOW;)
 888         osize += malloc_pagesize;
 889
 890         if (!malloc_realloc &&          /* unless we have to, */
 891       size <= osize &&          /* .. or are too small, */
 892       size > (osize - malloc_pagesize)) {   /* .. or can free a page, */
 893         return ptr;             /* don't do anything. */
 894     }
 895
 896     } else if (*mp >= MALLOC_MAGIC) {       /* Chunk allocation */
 897
 898     /* Check the pointer for sane values */
 899     if (((size_t)(uintptr_t)ptr & ((*mp)->size-1))) {
 900         wrtwarning("modified (chunk-) pointer.\n");
 901         return NULL;
 902     }
 903
 904     /* Find the chunk index in the page */
 905     i = ((size_t)(uintptr_t)ptr & malloc_pagemask) >> (*mp)->shift;
 906
 907     /* Verify that it isn't a free chunk already */
 908         if ((*mp)->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) {
 909         wrtwarning("chunk is already free.\n");
 910         return NULL;
 911     }
 912
 913     osize = (*mp)->size;
 914
 915     if (!malloc_realloc &&      /* Unless we have to, */
 916       size < osize &&       /* ..or are too small, */
 917       (size > osize/2 ||        /* ..or could use a smaller size, */
 918       osize == malloc_minsize)) {   /* ..(if there is one) */
 919         return ptr;         /* ..Don't do anything */
 920     }
 921
 922     } else {
 923     wrtwarning("pointer to wrong page.\n");
 924     return NULL;
 925     }
 926
 927     p = imalloc(size);
 928
 929     if (p != NULL) {
 930     /* copy the lesser of the two sizes, and free the old one */
 931     if (!size || !osize)
 932         ;
 933     else if (osize < size)
 934         memcpy(p, ptr, osize);
 935     else
 936         memcpy(p, ptr, size);
 937     ifree(ptr);
 938     }
 939     return p;
 940 }
 941
 942 /*
 943  * Free a sequence of pages
 944  */
 945
 946 static inline void
 947 free_pages(void *ptr, size_t idx, struct pginfo *info)
 948 {
 949     size_t i;
 950     struct pgfree *pf, *pt=NULL;
 951     size_t l;
 952     void *tail;
 953
 954     if (info == MALLOC_FREE) {
 955     wrtwarning("page is already free.\n");
 956     return;
 957     }
 958
 959     if (info != MALLOC_FIRST) {
 960     wrtwarning("pointer to wrong page.\n");
 961     return;
 962     }
 963
 964     if ((size_t)(uintptr_t)ptr & malloc_pagemask) {
 965     wrtwarning("modified (page-) pointer.\n");
 966     return;
 967     }
 968
 969     /* Count how many pages and mark them free at the same time */
 970     page_dir[idx] = MALLOC_FREE;
 971     for (i = 1; page_dir[idx+i] == MALLOC_FOLLOW; i++)
 972     page_dir[idx + i] = MALLOC_FREE;
 973
 974     l = i << malloc_pageshift;
 975
 976     if (malloc_junk)
 977     memset(ptr, SOME_FREE_JUNK, l);
 978
 979 /*    if (malloc_hint)
 980     madvise(ptr, l, MADV_FREE);*/
 981
 982     tail = (char *)ptr+l;
 983
 984     /* add to free-list */
 985     if (px == NULL)
 986     px = imalloc(sizeof *pt);   /* This cannot fail... */
 987     px->page = ptr;
 988     px->end =  tail;
 989     px->size = l;
 990     if (free_list.next == NULL) {
 991
 992     /* Nothing on free list, put this at head */
 993     px->next = free_list.next;
 994     px->prev = &free_list;
 995     free_list.next = px;
 996     pf = px;
 997     px = NULL;
 998
 999     } else {
1000
1001     /* Find the right spot, leave pf pointing to the modified entry. */
1002     tail = (char *)ptr+l;
1003
1004     for(pf = free_list.next; pf->end < ptr && pf->next != NULL;
1005         pf = pf->next)
1006         ; /* Race ahead here */
1007
1008     if (pf->page > tail) {
1009         /* Insert before entry */
1010         px->next = pf;
1011         px->prev = pf->prev;
1012         pf->prev = px;
1013         px->prev->next = px;
1014         pf = px;
1015         px = NULL;
1016     } else if (pf->end == ptr ) {
1017         /* Append to the previous entry */
1018         pf->end = (char *)pf->end + l;
1019         pf->size += l;
1020         if (pf->next != NULL && pf->end == pf->next->page ) {
1021         /* And collapse the next too. */
1022         pt = pf->next;
1023         pf->end = pt->end;
1024         pf->size += pt->size;
1025         pf->next = pt->next;
1026         if (pf->next != NULL)
1027             pf->next->prev = pf;
1028         }
1029     } else if (pf->page == tail) {
1030         /* Prepend to entry */
1031         pf->size += l;
1032         pf->page = ptr;
1033     } else if (pf->next == NULL) {
1034         /* Append at tail of chain */
1035         px->next = NULL;
1036         px->prev = pf;
1037         pf->next = px;
1038         pf = px;
1039         px = NULL;
1040     } else {
1041         wrterror("freelist is destroyed.\n");
1042     }
1043     }
1044
1045     /* Return something to OS ? */
1046     // FIXME für LOST
1047 #if 0
1048     if (pf->next == NULL &&         /* If we're the last one, */
1049       pf->size > malloc_cache &&        /* ..and the cache is full, */
1050       pf->end == malloc_brk &&          /* ..and none behind us, */
1051       malloc_brk == sbrk((intptr_t)0)) {    /* ..and it's OK to do... */
1052
1053     /*
1054      * Keep the cache intact.  Notice that the '>' above guarantees that
1055      * the pf will always have at least one page afterwards.
1056      */
1057     pf->end = (char *)pf->page + malloc_cache;
1058     pf->size = malloc_cache;
1059
1060     brk(pf->end);
1061     malloc_brk = pf->end;
1062
1063     idx = ptr2idx(pf->end);
1064
1065     for(i=idx;i <= last_idx;)
1066         page_dir[i++] = MALLOC_NOT_MINE;
1067
1068     last_idx = idx - 1;
1069
1070     /* XXX: We could realloc/shrink the pagedir here I guess. */
1071     }
1072 #endif
1073
1074     if (pt != NULL)
1075     ifree(pt);
1076 }
1077
1078 /*
1079  * Free a chunk, and possibly the page it's on, if the page becomes empty.
1080  */
1081
1082 static inline void
1083 free_bytes(void *ptr, size_t idx, struct pginfo *info)
1084 {
1085     size_t i;
1086     struct pginfo **mp;
1087     void *vp;
1088
1089     /* Find the chunk number on the page */
1090     i = ((size_t)(uintptr_t)ptr & malloc_pagemask) >> info->shift;
1091
1092     if (((size_t)(uintptr_t)ptr & (info->size-1))) {
1093     wrtwarning("modified (chunk-) pointer.\n");
1094     return;
1095     }
1096
1097     if (info->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) {
1098     wrtwarning("chunk is already free.\n");
1099     return;
1100     }
1101
1102     if (malloc_junk)
1103     memset(ptr, SOME_FREE_JUNK, (size_t)info->size);
1104
1105     info->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS);
1106     info->free++;
1107
1108     mp = page_dir + info->shift;
1109
1110     if (info->free == 1) {
1111
1112     /* Page became non-full */
1113
1114     mp = page_dir + info->shift;
1115     /* Insert in address order */
1116     while (*mp && (*mp)->next && (*mp)->next->page < info->page)
1117         mp = &(*mp)->next;
1118     info->next = *mp;
1119     *mp = info;
1120     return;
1121     }
1122
1123     if (info->free != info->total)
1124     return;
1125
1126     /* Find & remove this page in the queue */
1127     while (*mp != info) {
1128     mp = &((*mp)->next);
1129 #ifdef MALLOC_EXTRA_SANITY
1130     if (!*mp)
1131         wrterror("(ES): Not on queue.\n");
1132 #endif /* MALLOC_EXTRA_SANITY */
1133     }
1134     *mp = info->next;
1135
1136     /* Free the page & the info structure if need be */
1137     page_dir[idx] = MALLOC_FIRST;
1138     vp = info->page;        /* Order is important ! */
1139     if(vp != (void*)info)
1140     ifree(info);
1141     ifree(vp);
1142 }
1143
1144 static void
1145 ifree(void *ptr)
1146 {
1147     struct pginfo *info;
1148     size_t idx;
1149
1150     /* This is legal */
1151     if (ptr == NULL)
1152     return;
1153
1154     /* If we're already sinking, don't make matters any worse. */
1155     if (suicide)
1156     return;
1157
1158     idx = ptr2idx(ptr);
1159
1160     if (idx < malloc_pageshift) {
1161     wrtwarning("junk pointer, too low to make sense.\n");
1162     return;
1163     }
1164
1165     if (idx > last_idx) {
1166     wrtwarning("junk pointer, too high to make sense.\n");
1167     return;
1168     }
1169
1170     info = page_dir[idx];
1171
1172     if (info < MALLOC_MAGIC)
1173         free_pages(ptr, idx, info);
1174     else
1175     free_bytes(ptr, idx, info);
1176     return;
1177 }
1178
1179 /*
1180  * These are the public exported interface routines.
1181  */
1182
1183
1184 void *
1185 malloc(size_t size)
1186 {
1187     void *r;
1188     //printf("malloc(%d) => ", size);
1189
1190     THREAD_LOCK();
1191     malloc_func = " in malloc():";
1192     if (malloc_active++) {
1193         wrtwarning("recursive call.\n");
1194         malloc_active--;
1195         THREAD_UNLOCK();
1196         //printf("= NULL [a]\n");
1197         return (NULL);
1198     }
1199
1200     if (!malloc_started)
1201         malloc_init();
1202
1203     if (malloc_sysv && !size)
1204         r = NULL;
1205     else
1206         r = imalloc(size);
1207
1208     UTRACE(0, size, r);
1209     malloc_active--;
1210     THREAD_UNLOCK();
1211     if (r == NULL && (size != 0 || !malloc_sysv)) {
1212         if (malloc_xmalloc)
1213             wrterror("out of memory.\n");
1214         errno = ENOMEM;
1215     }
1216     //printf("= 0x%x\n", r);
1217     return (r);
1218 }
1219
1220 void
1221 free(void *ptr)
1222 {
1223     THREAD_LOCK();
1224     malloc_func = " in free():";
1225     if (malloc_active++) {
1226     wrtwarning("recursive call.\n");
1227     malloc_active--;
1228     THREAD_UNLOCK();
1229     return;
1230     }
1231     if (!malloc_started)
1232     malloc_init();
1233     ifree(ptr);
1234     UTRACE(ptr, 0, 0);
1235     malloc_active--;
1236     THREAD_UNLOCK();
1237     return;
1238 }
1239
1240 void *
1241 realloc(void *ptr, size_t size)
1242 {
1243     void *r;
1244
1245     THREAD_LOCK();
1246     malloc_func = " in realloc():";
1247     if (malloc_active++) {
1248     wrtwarning("recursive call.\n");
1249         malloc_active--;
1250     THREAD_UNLOCK();
1251     return (NULL);
1252     }
1253     if (!malloc_started)
1254     malloc_init();
1255     if (malloc_sysv && !size) {
1256     ifree(ptr);
1257     r = NULL;
1258     } else if (!ptr) {
1259     r = imalloc(size);
1260     } else {
1261         r = irealloc(ptr, size);
1262     }
1263     UTRACE(ptr, size, r);
1264     malloc_active--;
1265     THREAD_UNLOCK();
1266     if (r == NULL && (size != 0 || !malloc_sysv)) {
1267     if (malloc_xmalloc)
1268         wrterror("out of memory.\n");
1269     errno = ENOMEM;
1270     }
1271     return (r);
1272 }
1273
1274
1275 #include <string.h>
1276
1277 void *calloc(size_t nmemb, size_t size) {
1278     void* ptr = malloc(nmemb * size);
1279     memset(ptr, 0, nmemb * size);
1280     return ptr;
1281 }
1282