lang/cem/libcc.ansi/stdlib/malloc.c

   1
   2 /**********************************************************/
   3 /*
   4 /*               This was file READ_ME
   5 /*
   6 /**********************************************************/
   7
   8 /*
   9         PROGRAM
  10                 malloc(), free(), realloc()
  11         AUTHOR
  12                 Dick Grune, Free University, Amsterdam
  13                 Modified by Ceriel Jacobs, Free University, Amsterdam,
  14                 to make it faster
  15         VERSION
  16                 $Id: READ_ME,v 1.2 1994/06/24 11:55:09 ceriel Exp $
  17         DESCRIPTION
  18         This is an independent rewrite of the malloc/free package; it is
  19         fast and efficient.  Free blocks are kept in doubly linked lists,
  20         list N holding blocks with sizes between 2**N and 2**(N+1)-1.
  21         Consequently neither malloc nor free have to do any searching:
  22         the cost of a call of malloc() (or free()) is constant, however
  23         many blocks you have got.
  24
  25         If you switch on the NON_STANDARD macro (see param.h) every block
  26         costs 2 pointers overhead (otherwise it's 4).
  27 */
  28 /*
  29         There is an organisational problem here: during devellopment
  30         I want the package divided into modules, which implies external
  31         names for the communication.  The only external names I want in
  32         the finished product are malloc, realloc and free.  This requires
  33         some hanky-panky.
  34 */
  35
  36
  37 /**********************************************************/
  38 /*
  39 /*               This was file size_type.h
  40 /*
  41 /**********************************************************/
  42
  43 #if     _EM_WSIZE == _EM_PSIZE
  44 typedef unsigned int size_type;
  45 #elif   _EM_LSIZE == _EM_PSIZE
  46 typedef unsigned long size_type;
  47 #else
  48 #error funny pointer size
  49 #endif
  50 #include        <stdlib.h>
  51
  52
  53 /**********************************************************/
  54 /*
  55 /*               This was file param.h
  56 /*
  57 /**********************************************************/
  58
  59 /* $Id: param.h,v 1.2 1994/06/24 11:55:32 ceriel Exp $ */
  60 /*
  61  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  62  * See the copyright notice in the ACK home directory, in the file "Copyright".
  63  */
  64
  65 #       define  NON_STANDARD    /*      If defined, the contents of a block
  66                                         will NOT be left undisturbed after it
  67                                         is freed, as opposed to what it says
  68                                         in the manual (malloc(2)).
  69                                         Setting this option reduces the memory
  70                                         overhead considerably.  I personally
  71                                         consider the specified behaviour an
  72                                         artefact of the original
  73                                         implementation.
  74                                 */
  75
  76 #       undef   ASSERT          /*      If defined, some inexpensive tests
  77                                         will be made to ensure the
  78                                         correctness of some sensitive data.
  79                                         It often turns an uncontrolled crash
  80                                         into a controlled one.
  81                                 */
  82
  83 #       undef   CHECK           /*      If defined, extensive and expensive
  84                                         tests will be done, inculding a
  85                                         checksum on the mallinks (chunk
  86                                         information blocks).  The resulting
  87                                         information will be printed on a file
  88                                         called mal.out .
  89                                         Additionally a function
  90                                                 maldump(n) int n;
  91                                         will be defined, which will dump
  92                                         pertinent info in pseudo-readable
  93                                         form; it aborts afterwards if n != 0.
  94                                 */
  95
  96 #       undef   EXTERN          /*      If defined, all static names will
  97                                         become extern, which is a help in
  98                                         using adb(1) or prof(1)
  99                                 */
 100
 101 #       define  STORE           /*      If defined, separate free lists will
 102                                         be kept of chunks with small sizes,
 103                                         to speed things up a little.
 104                                 */
 105
 106 #       undef SYSTEM            /*      If defined, the system module is used.
 107                                         Otherwise, "sbrk" is called directly.
 108                                 */
 109
 110 #define ALIGNMENT       8
 111                                 /* alignment common to all types */
 112 #define LOG_MIN_SIZE    3
 113 #define LOG_MAX_SIZE    24
 114
 115
 116 /**********************************************************/
 117 /*
 118 /*               This was file impl.h
 119 /*
 120 /**********************************************************/
 121
 122 /* $Id: impl.h,v 1.3 1994/06/24 11:55:21 ceriel Exp $ */
 123 /*
 124  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 125  * See the copyright notice in the ACK home directory, in the file "Copyright".
 126  */
 127 /*      This file essentially describes how the mallink info block
 128         is implemented.
 129 */
 130
 131 #define MIN_SIZE        (1<<LOG_MIN_SIZE)
 132 #define MAX_FLIST       (LOG_MAX_SIZE - LOG_MIN_SIZE)
 133 #if ALIGNMENT != 4 && ALIGNMENT != 8 && ALIGNMENT != 16
 134 #error ALIGNMENT must be 4, 8 or 16
 135 #elif ALIGNMENT % _EM_LSIZE
 136 /* since calloc() does it's initialization in longs */
 137 #error ALIGNMENT must be a multiple of the long size
 138 #endif
 139 #define align(n)        (((n) + (ALIGNMENT - 1)) & ~(ALIGNMENT - 1))
 140
 141 union _inf {
 142         union _inf *ptr;
 143         size_type ui;
 144 };
 145
 146 typedef union _inf mallink;
 147 #define MAL_NULL        ((mallink *)0)
 148
 149 /*      Access macros; only these macros know where to find values.
 150         They are also lvalues.
 151 */
 152 #ifndef NON_STANDARD
 153 #define OFF_SET 0
 154 #else   /* def NON_STANDARD */
 155 #define OFF_SET 2
 156 #endif  /* NON_STANDARD */
 157
 158 #define _log_prev_of(ml)        ((ml)[-1+OFF_SET]).ptr
 159 #define _log_next_of(ml)        ((ml)[-2+OFF_SET]).ptr
 160 #define _phys_prev_of(ml)       ((ml)[-3+OFF_SET]).ptr
 161 #define _this_size_of(ml)       ((ml)[-4+OFF_SET]).ui
 162 #ifndef CHECK
 163 #define N_WORDS                 4
 164 #else   /* ifdef        CHECK */
 165 #define _checksum_of(ml)        ((ml)[-5+OFF_SET]).ui
 166 #define _print_of(ml)           ((ml)[-6+OFF_SET]).ui
 167 #define _mark_of(ml)            ((ml)[-7+OFF_SET]).ui
 168 #define N_WORDS                 7
 169 #endif  /* CHECK */
 170
 171 #define mallink_size()          (size_t) \
 172         align((N_WORDS - OFF_SET) * sizeof (mallink))
 173
 174 #ifdef  CHECK
 175 #define set_mark(ml,e)          (_mark_of(ml) = (e))
 176 #define mark_of(ml)             (_mark_of(ml))
 177
 178 #define set_checksum(ml,e)      (_checksum_of(ml) = (e))
 179 #define checksum_of(ml)         (_checksum_of(ml))
 180 #endif  /* CHECK */
 181
 182 #define new_mallink(ml)         ( _log_prev_of(ml) = 0, \
 183                                   _log_next_of(ml) = 0, \
 184                                   _phys_prev_of(ml) = 0, \
 185                                   _this_size_of(ml) = 0 )
 186
 187 #define block_of_mallink(ml)    ((void *)ml)
 188 #define mallink_of_block(addr)  ((mallink *)addr)
 189
 190 #define public  extern
 191 #define publicdata      extern
 192 #ifndef EXTERN
 193 #define private static
 194 #define privatedata     static
 195 #else   /* def  EXTERN */
 196 #define private extern
 197 #define privatedata
 198 #endif  /* EXTERN */
 199
 200 #ifdef  ASSERT
 201 private m_assert(const char *fn, int ln);
 202 #define assert(b)               (!(b) ? m_assert(__FILE__, __LINE__) : 0)
 203 #else   /* ndef ASSERT */
 204 #define assert(b)               0
 205 #endif  /* ASSERT */
 206
 207
 208 /**********************************************************/
 209 /*
 210 /*               This was file check.h
 211 /*
 212 /**********************************************************/
 213
 214 /* $Id: check.h,v 1.2 1994/06/24 11:55:15 ceriel Exp $ */
 215 /*
 216  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 217  * See the copyright notice in the ACK home directory, in the file "Copyright".
 218  */
 219 #ifdef  CHECK
 220
 221 private check_mallinks(const char *s), calc_checksum(mallink *ml);
 222 private check_work_empty(const char *s);
 223 private started_working_on(mallink *ml), stopped_working_on(mallink *ml);
 224
 225 #else   /* ifndef       CHECK */
 226
 227 #define maldump(n)              abort()
 228 #define check_mallinks(s)       0
 229 #define calc_checksum(ml)       0
 230 #define started_working_on(ml)  0
 231 #define stopped_working_on(ml)  0
 232 #define check_work_empty(s)     0
 233
 234 #endif  /* CHECK */
 235
 236
 237 /**********************************************************/
 238 /*
 239 /*               This was file log.h
 240 /*
 241 /**********************************************************/
 242
 243 /* $Id: log.h,v 1.2 1994/06/24 11:55:26 ceriel Exp $ */
 244 /*
 245  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 246  * See the copyright notice in the ACK home directory, in the file "Copyright".
 247  */
 248 /*      Algorithms to manipulate the doubly-linked lists of free
 249         chunks.
 250 */
 251
 252 private link_free_chunk(mallink *ml), unlink_free_chunk(mallink *ml);
 253 private mallink *first_present(int class);
 254 private mallink *search_free_list(int class, size_t n);
 255
 256 #ifdef STORE
 257 #define in_store(ml)            ((size_type)_phys_prev_of(ml) & STORE_BIT)
 258 #define set_store(ml, e) \
 259         (_phys_prev_of(ml) = (mallink *) \
 260                 ((e) ? (size_type) _phys_prev_of(ml) | STORE_BIT : \
 261                        (size_type) _phys_prev_of(ml) & ~STORE_BIT))
 262 #endif
 263 #define set_log_prev(ml,e)      (_log_prev_of(ml) = (e))
 264 #define log_prev_of(ml)         (mallink *) (_log_prev_of(ml))
 265
 266 #define set_log_next(ml,e)      (_log_next_of(ml) = (e))
 267 #define log_next_of(ml)         (mallink *) (_log_next_of(ml))
 268
 269
 270
 271 /**********************************************************/
 272 /*
 273 /*               This was file phys.h
 274 /*
 275 /**********************************************************/
 276
 277 /* $Id: phys.h,v 1.4 1994/06/24 11:55:38 ceriel Exp $ */
 278 /*
 279  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 280  * See the copyright notice in the ACK home directory, in the file "Copyright".
 281  */
 282 /*      Algorithms to manipulate the doubly-linked list of physical
 283         chunks.
 284 */
 285 privatedata mallink *ml_last;
 286
 287 #define FREE_BIT                01
 288 #ifdef STORE
 289 #define STORE_BIT               02
 290 #define BITS                    (FREE_BIT|STORE_BIT)
 291 #else
 292 #define BITS                    (FREE_BIT)
 293 #endif
 294
 295 #define __bits(ml)              ((int)((size_type)_phys_prev_of(ml) & BITS))
 296 #define __free_of(ml)           ((int)((size_type)_phys_prev_of(ml) & FREE_BIT))
 297 #define __phys_prev_of(ml)      ((mallink *)((size_type)_phys_prev_of(ml) & ~BITS))
 298 #define prev_size_of(ml)        ((char *)(ml) - \
 299                                  (char *)__phys_prev_of(ml) - \
 300                                  mallink_size() \
 301                                 )
 302 #define set_phys_prev(ml,e) \
 303         (_phys_prev_of(ml) = (mallink *) ((char *)e + __bits(ml)))
 304
 305 #ifdef  CHECK
 306 private Error(const char *fmt, const char *s, mallink *ml);
 307 #define phys_prev_of(ml)        (mallink *) \
 308         (first_mallink(ml) ? \
 309                 (char *)Error("phys_prev_of first_mallink %p", "somewhere", ml) : \
 310                 (char *)__phys_prev_of(ml) \
 311         )
 312 #else   /* ndef CHECK */
 313 #define phys_prev_of(ml)        __phys_prev_of(ml)
 314 #endif  /* CHECK */
 315
 316 #define first_mallink(ml)       (int) (__phys_prev_of(ml) == 0)
 317 #define last_mallink(ml)        (int) ((ml) == ml_last)
 318
 319 /*      There is an ambiguity in the semantics of phys_next_of: sometimes
 320         one wants it to return MAL_NULL if there is no next chunk, at
 321         other times one wants the address of the virtual chunk at the
 322         end of memory.  The present version returns the address of the
 323         (virtual) chunk and relies on the user to test last_mallink(ml)
 324         first.
 325 */
 326 #define size_of(ml)             (_this_size_of(ml) - mallink_size())
 327 #define set_phys_next(ml,e) \
 328         (_this_size_of(ml) = (size_type)((char *)(e) - (char *)(ml)))
 329 #define phys_next_of(ml)        (mallink *) ((char *)(ml) + _this_size_of(ml))
 330
 331 #define set_free(ml,e) \
 332         (_phys_prev_of(ml) = (mallink *) \
 333                 ((e) ? (size_type) _phys_prev_of(ml) | FREE_BIT : \
 334                        (size_type) _phys_prev_of(ml) & ~FREE_BIT))
 335 #define free_of(ml)             (__free_of(ml))
 336
 337 #define coalesce_forw(ml,nxt)   ( unlink_free_chunk(nxt), \
 338                                   combine_chunks((ml), (nxt)))
 339
 340 #define coalesce_backw(ml,prv)  ( unlink_free_chunk(prv), \
 341                                   stopped_working_on(ml), \
 342                                   combine_chunks((prv), (ml)), \
 343                                   started_working_on(prv))
 344
 345 #ifdef  CHECK
 346 #define set_print(ml,e)         (_print_of(ml) = (e))
 347 #define print_of(ml)            (_print_of(ml))
 348 #endif  /* CHECK */
 349
 350 private truncate(mallink *ml, size_t size);
 351 private combine_chunks(register mallink *ml1, register mallink *ml2);
 352 private mallink *create_chunk(void *p, size_t n);
 353
 354
 355 /**********************************************************/
 356 /*
 357 /*               This was file mal.c
 358 /*
 359 /**********************************************************/
 360
 361 /* $Id: mal.c,v 1.5 1994/06/24 11:55:29 ceriel Exp $ */
 362 /*
 363  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 364  * See the copyright notice in the ACK home directory, in the file "Copyright".
 365  */
 366 #include        <limits.h>
 367 #include        <stdlib.h>
 368
 369 /*      Malloc space is traversed by N doubly-linked lists of chunks, each
 370         containing a couple of house-keeping data addressed as a
 371         'mallink' and a piece of useful space, called the block.
 372         The N lists are accessed through their starting pointers in
 373         free_list[].  Free_list[n] points to a list of chunks between
 374         2**(n+LOG_MIN_SIZE) and 2**(n+LOG_MIN_SIZE+1)-1, which means
 375         that the smallest chunk is 2**LOG_MIN_SIZE (== MIN_SIZE).
 376 */
 377
 378 #ifdef SYSTEM
 379 #include        <system.h>
 380 #define SBRK    sys_break
 381 #else
 382 #define SBRK    _sbrk
 383 #define ILL_BREAK               (void *)(-1)    /* funny failure value */
 384 #endif
 385 extern void *SBRK(int incr);
 386 #ifdef STORE
 387 #define MAX_STORE       32
 388 private do_free(mallink *ml), sell_out(void);
 389 privatedata mallink *store[MAX_STORE];
 390 #endif /* STORE */
 391
 392 void *
 393 malloc(register size_t n)
 394 {check_mallinks("malloc entry");{
 395         register mallink *ml;
 396         register int min_class;
 397
 398         if (n == 0) {
 399                 return NULL;
 400         }
 401         if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
 402 #ifdef STORE
 403         if (n <= MAX_STORE*MIN_SIZE)    {
 404                 /* look in the store first */
 405                 register mallink **stp = &store[(n >> LOG_MIN_SIZE) - 1];
 406
 407                 if (ml = *stp)  {
 408                         *stp = log_next_of(ml);
 409                         set_store(ml, 0);
 410                         check_mallinks("malloc fast exit");
 411                         assert(! in_store(ml));
 412                         return block_of_mallink(ml);
 413                 }
 414         }
 415 #endif /* STORE */
 416
 417         check_work_empty("malloc, entry");
 418
 419         /*      Acquire a chunk of at least size n if at all possible;
 420                 Try everything.
 421         */
 422         {
 423                 /*      Inline substitution of "smallest".
 424                 */
 425                 register size_t n1 = n;
 426
 427                 assert(n1 < (1L << LOG_MAX_SIZE));
 428                 min_class = 0;
 429
 430                 do {
 431                         n1 >>= 1;
 432                         min_class++;
 433                 } while (n1 >= MIN_SIZE);
 434         }
 435
 436         if (min_class >= MAX_FLIST)
 437                 return NULL;            /* we don't deal in blocks that big */
 438         ml = first_present(min_class);
 439         if (ml == MAL_NULL)     {
 440                 /*      Try and extend */
 441                 register void *p;
 442 #define GRABSIZE        4096            /* Power of 2 */
 443                 register size_t req =
 444                         ((MIN_SIZE<<min_class)+ mallink_size() + GRABSIZE - 1) &
 445                                 ~(GRABSIZE-1);
 446
 447                 if (!ml_last)   {
 448                         /* first align SBRK() */
 449
 450                         p = SBRK(0);
 451                         SBRK((int) (align((size_type) p) - (size_type) p));
 452                 }
 453
 454                 /* SBRK takes an int; sorry ... */
 455                 if ((int) req < 0) {
 456                         p = ILL_BREAK;
 457                 } else {
 458                         p = SBRK((int)req);
 459                 }
 460                 if (p == ILL_BREAK) {
 461                         req = n + mallink_size();
 462                         if ((int) req >= 0) p = SBRK((int)req);
 463                 }
 464                 if (p == ILL_BREAK)     {
 465                         /*      Now this is bad.  The system will not give us
 466                                 more memory.  We can only liquidate our store
 467                                 and hope it helps.
 468                         */
 469 #ifdef STORE
 470                         sell_out();
 471                         ml = first_present(min_class);
 472                         if (ml == MAL_NULL)     {
 473 #endif /* STORE */
 474                                 /* In this emergency we try to locate a suitable
 475                                    chunk in the free_list just below the safe
 476                                    one; some of these chunks may fit the job.
 477                                 */
 478                                 ml = search_free_list(min_class - 1, n);
 479                                 if (!ml)        /* really out of space */
 480                                         return NULL;
 481                                 started_working_on(ml);
 482                                 unlink_free_chunk(ml);
 483                                 check_mallinks("suitable_chunk, forced");
 484 #ifdef STORE
 485                         }
 486                         else started_working_on(ml);
 487 #endif /* STORE */
 488                 }
 489                 else {
 490                         assert((size_type)p == align((size_type)p));
 491                         ml = create_chunk(p, req);
 492                 }
 493                 check_mallinks("suitable_chunk, extended");
 494         }
 495         else started_working_on(ml);
 496
 497         /* we have a chunk */
 498         set_free(ml, 0);
 499         calc_checksum(ml);
 500         check_mallinks("suitable_chunk, removed");
 501         n += mallink_size();
 502         if (n + MIN_SIZE <= size_of(ml)) {
 503                 truncate(ml, n);
 504         }
 505         stopped_working_on(ml);
 506         check_mallinks("malloc exit");
 507         check_work_empty("malloc exit");
 508 #ifdef STORE
 509         assert(! in_store(ml));
 510 #endif
 511         return block_of_mallink(ml);
 512 }}
 513
 514 void
 515 free(void *addr)
 516 {check_mallinks("free entry");{
 517         register mallink *ml;
 518
 519         if (addr == NULL) {
 520                 check_mallinks("free(0) very fast exit");
 521                 return;
 522         }
 523
 524         ml = mallink_of_block(addr);
 525 #ifdef STORE
 526
 527         if (free_of(ml) || in_store(ml))
 528                 return;                         /* user frees free block */
 529         if (size_of(ml) <= MAX_STORE*MIN_SIZE)  {
 530                 /* return to store */
 531                 mallink **stp = &store[(size_of(ml) >> LOG_MIN_SIZE) - 1];
 532
 533                 set_log_next(ml, *stp);
 534                 *stp = ml;
 535                 set_store(ml, 1);
 536                 calc_checksum(ml);
 537                 check_mallinks("free fast exit");
 538         }
 539         else    {
 540                 do_free(ml);
 541                 check_mallinks("free exit");
 542         }
 543 }}
 544
 545 private
 546 do_free(register mallink *ml)
 547 {{
 548 #endif
 549
 550 #ifndef STORE
 551         if (free_of(ml))        return;
 552 #endif /* STORE */
 553         started_working_on(ml);
 554         set_free(ml, 1);
 555         calc_checksum(ml);
 556         if (! last_mallink(ml)) {
 557                 register mallink *next = phys_next_of(ml);
 558
 559                 if (free_of(next)) coalesce_forw(ml, next);
 560         }
 561
 562         if (! first_mallink(ml)) {
 563                 register mallink *prev = phys_prev_of(ml);
 564
 565                 if (free_of(prev)) {
 566                         coalesce_backw(ml, prev);
 567                         ml = prev;
 568                 }
 569         }
 570         link_free_chunk(ml);
 571         stopped_working_on(ml);
 572         check_work_empty("free");
 573
 574         /* Compile-time checks on param.h */
 575         switch (0)      {
 576         case MIN_SIZE < OFF_SET * sizeof(mallink):      break;
 577         case 1: break;
 578         /*      If this statement does not compile due to duplicate case
 579                 entry, the minimum size block cannot hold the links for
 580                 the free blocks.  Either raise LOG_MIN_SIZE or switch
 581                 off NON_STANDARD.
 582         */
 583         }
 584         switch(0)       {
 585         case sizeof(void *) != sizeof(size_type):       break;
 586         case 1: break;
 587         /*      If this statement does not compile due to duplicate
 588                 case entry, size_type is not defined correctly.
 589                 Redefine and compile again.
 590         */
 591         }
 592 }}
 593
 594 void *
 595 realloc(void *addr, register size_t n)
 596 {check_mallinks("realloc entry");{
 597         register mallink *ml, *ph_next;
 598         register size_type size;
 599
 600         if (addr == NULL) {
 601                 /*      Behave like most Unix realloc's when handed a
 602                         null-pointer
 603                 */
 604                 return malloc(n);
 605         }
 606         if (n == 0) {
 607                 free(addr);
 608                 return NULL;
 609         }
 610         ml = mallink_of_block(addr);
 611         if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
 612 #ifdef STORE
 613         if (in_store(ml)) {
 614                 register mallink *stp = store[(size_of(ml) >> LOG_MIN_SIZE) - 1];
 615                 mallink *stp1 = NULL;
 616                 while (ml != stp)       {
 617                         stp1 = stp;
 618                         stp = log_next_of(stp);
 619                 }
 620                 stp = log_next_of(stp);
 621                 if (! stp1) store[(size_of(ml) >> LOG_MIN_SIZE) - 1] = stp;
 622                 else set_log_next(stp1, stp);
 623                 set_store(ml, 0);
 624                 calc_checksum(ml);
 625         }
 626 #endif
 627         if (free_of(ml)) {
 628                 unlink_free_chunk(ml);
 629                 set_free(ml, 0);                /* user reallocs free block */
 630         }
 631         started_working_on(ml);
 632         size = size_of(ml);
 633         if (    /* we can simplify the problem by adding the next chunk: */
 634                 n > size &&
 635                 !last_mallink(ml) &&
 636                 (ph_next = phys_next_of(ml), free_of(ph_next)) &&
 637                 n <= size + mallink_size() + size_of(ph_next)
 638         )       {
 639                 /* add in the physically next chunk */
 640                 unlink_free_chunk(ph_next);
 641                 combine_chunks(ml, ph_next);
 642                 size = size_of(ml);
 643                 check_mallinks("realloc, combining");
 644         }
 645         if (n > size)   {               /* this didn't help */
 646                 void *new;
 647                 register char *l1, *l2 = addr;
 648
 649                 stopped_working_on(ml);
 650                 if (!(new = l1 = malloc(n))) return NULL;       /* no way */
 651                 while (size--) *l1++ = *l2++;
 652                 free(addr);
 653                 check_work_empty("mv_realloc");
 654 #ifdef STORE
 655                 assert(! in_store(mallink_of_block(new)));
 656 #endif
 657                 return new;
 658         }
 659         /* it helped, but maybe too well */
 660         n += mallink_size();
 661         if (n + MIN_SIZE <= size_of(ml)) {
 662                 truncate(ml, n);
 663         }
 664         stopped_working_on(ml);
 665         check_mallinks("realloc exit");
 666         check_work_empty("realloc");
 667 #ifdef STORE
 668         assert(! in_store(ml));
 669 #endif
 670         return addr;
 671 }}
 672
 673 void *
 674 calloc(size_t nmemb, size_t size)
 675 {check_mallinks("calloc entry");{
 676         long *l1, *l2;
 677         size_t n;
 678
 679         if (size == 0) return NULL;
 680         if (nmemb == 0) return NULL;
 681
 682         /* Check for overflow on the multiplication. The peephole-optimizer
 683          * will eliminate all but one of the possibilities.
 684          */
 685         if (sizeof(size_t) == sizeof(int)) {
 686                 if (UINT_MAX / size < nmemb) return NULL;
 687         } else if (sizeof(size_t) == sizeof(long)) {
 688                 if (ULONG_MAX / size < nmemb) return NULL;
 689         } else return NULL;             /* can't happen, can it ? */
 690
 691         n = size * nmemb;
 692         if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
 693         if (n >= (1L << LOG_MAX_SIZE)) return NULL;
 694         l1 = (long *) malloc(n);
 695         l2 = l1 + (n / sizeof(long));   /* n is at least long aligned */
 696         while ( l2 != l1 ) *--l2 = 0;
 697         check_mallinks("calloc exit");
 698         check_work_empty("calloc exit");
 699         return (void *)l1;
 700 }}
 701 /*      Auxiliary routines */
 702
 703 #ifdef STORE
 704 private
 705 sell_out(void)  {
 706         /*      Frees all block in store.
 707         */
 708         register mallink **stp;
 709
 710         for (stp = &store[0]; stp < &store[MAX_STORE]; stp++)   {
 711                 register mallink *ml = *stp;
 712
 713                 while (ml)      {
 714                         *stp = log_next_of(ml);
 715                         set_store(ml, 0);
 716                         do_free(ml);
 717                         ml = *stp;
 718                 }
 719         }
 720
 721 }
 722 #endif /* STORE */
 723
 724 #ifdef  ASSERT
 725 private
 726 m_assert(const char *fn, int ln)
 727 {
 728         char ch;
 729
 730         while (*fn)
 731                 write(2, fn++, 1);
 732         write(2, ": malloc assert failed in line ", 31);
 733         ch = (ln / 100) + '0'; write(2, &ch, 1); ln %= 100;
 734         ch = (ln / 10) + '0'; write(2, &ch, 1); ln %= 10;
 735         ch = (ln / 1) + '0'; write(2, &ch, 1);
 736         write(2, "\n", 1);
 737         maldump(1);
 738 }
 739 #endif  /* ASSERT */
 740
 741
 742 /**********************************************************/
 743 /*
 744 /*               This was file log.c
 745 /*
 746 /**********************************************************/
 747
 748 /* $Id: log.c,v 1.4 1994/06/24 11:55:23 ceriel Exp $ */
 749 /*
 750  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 751  * See the copyright notice in the ACK home directory, in the file "Copyright".
 752  */
 753
 754 /*      Logical manipulations.
 755         The chunks are properly chained in the physical chain.
 756 */
 757
 758 privatedata mallink *free_list[MAX_FLIST+1];
 759
 760 private
 761 link_free_chunk(register mallink *ml)
 762 {
 763         /*      The free chunk ml is inserted in its proper logical
 764                 chain.
 765         */
 766         register mallink **mlp = &free_list[0];
 767         register size_type n = size_of(ml);
 768         register mallink *ml1;
 769
 770         assert(n < (1L << LOG_MAX_SIZE));
 771
 772         do {
 773                 n >>= 1;
 774                 mlp++;
 775         }
 776         while (n >= MIN_SIZE);
 777
 778         ml1 = *--mlp;
 779         set_log_prev(ml, MAL_NULL);
 780         set_log_next(ml, ml1);
 781         calc_checksum(ml);
 782         if (ml1) {
 783                 /* link backwards
 784                 */
 785                 set_log_prev(ml1, ml);
 786                 calc_checksum(ml1);
 787         }
 788         *mlp = ml;
 789 }
 790
 791 private
 792 unlink_free_chunk(register mallink *ml)
 793 {
 794         /*      Unlinks a free chunk from (the middle of) the
 795                 logical chain.
 796         */
 797         register mallink *next = log_next_of(ml);
 798         register mallink *prev = log_prev_of(ml);
 799
 800         if (!prev)      {
 801                 /* it is the first in the chain */
 802                 register mallink **mlp = &free_list[-1];
 803                 register size_type n = size_of(ml);
 804
 805                 assert(n < (1L << LOG_MAX_SIZE));
 806                 do {
 807                         n >>= 1;
 808                         mlp++;
 809                 }
 810                 while (n >= MIN_SIZE);
 811                 *mlp = next;
 812         }
 813         else    {
 814                 set_log_next(prev, next);
 815                 calc_checksum(prev);
 816         }
 817         if (next) {
 818                 set_log_prev(next, prev);
 819                 calc_checksum(next);
 820         }
 821 }
 822
 823 private mallink *
 824 search_free_list(int class, size_t n)
 825 {
 826         /*      Searches the free_list[class] for a chunk of at least size n;
 827                 since it is searching a slightly undersized list,
 828                 such a block may not be there.
 829         */
 830         register mallink *ml;
 831
 832         for (ml = free_list[class]; ml; ml = log_next_of(ml))
 833                 if (size_of(ml) >= n)
 834                         return ml;
 835         return MAL_NULL;                /* nothing found */
 836 }
 837
 838 private mallink *
 839 first_present(int class)
 840 {
 841         /*      Find the index i in free_list[] such that:
 842                         i >= class && free_list[i] != MAL_NULL.
 843                 Return MAL_NULL if no such i exists;
 844                 Otherwise, return the first block of this list, after
 845                 unlinking it.
 846         */
 847         register mallink **mlp, *ml;
 848
 849         for (mlp = &free_list[class]; mlp < &free_list[MAX_FLIST]; mlp++) {
 850                 if ((ml = *mlp) != MAL_NULL)    {
 851
 852                         *mlp = log_next_of(ml); /* may be MAL_NULL */
 853                         if (*mlp) {
 854                                 /* unhook backward link
 855                                 */
 856                                 set_log_prev(*mlp, MAL_NULL);
 857                                 calc_checksum(*mlp);
 858                         }
 859                         return ml;
 860                 }
 861         }
 862         return MAL_NULL;
 863 }
 864
 865 #ifdef  CHECK
 866 private mallink *
 867 free_list_entry(int i)  {
 868         /*      To allow maldump.c access to log.c's private data.
 869         */
 870         return free_list[i];
 871 }
 872 #endif  /* CHECK */
 873
 874
 875 /**********************************************************/
 876 /*
 877 /*               This was file phys.c
 878 /*
 879 /**********************************************************/
 880
 881 /* $Id: phys.c,v 1.2 1994/06/24 11:55:35 ceriel Exp $ */
 882 /*
 883  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 884  * See the copyright notice in the ACK home directory, in the file "Copyright".
 885  */
 886 #include        <stdlib.h>
 887
 888 /*      Physical manipulations.
 889         The blocks concerned are not in any logical chain.
 890 */
 891
 892 private mallink *
 893 create_chunk(void *p, size_t n)
 894 {
 895         /*      The newly acquired piece of memory at p, of length n,
 896                 is turned into a free chunk, properly chained in the
 897                 physical chain.
 898                 The address of the chunk is returned.
 899         */
 900         register mallink *ml;
 901         /*      All of malloc memory is followed by a virtual chunk, the
 902                 mallink of which starts mallink_size() bytes past the last
 903                 byte in memory.
 904                 Its use is prevented by testing for ml == ml_last first.
 905         */
 906         register mallink *last = ml_last;
 907
 908         assert(!last || p == (char *)phys_next_of(last) - mallink_size());
 909         ml = (mallink *)((char *)p + mallink_size());   /* bump ml */
 910         new_mallink(ml);
 911         started_working_on(ml);
 912         set_free(ml, 1);
 913         set_phys_prev(ml, last);
 914         ml_last = ml;
 915
 916         set_phys_next(ml, (mallink *)((char *)ml + n));
 917         calc_checksum(ml);
 918         assert(size_of(ml) + mallink_size() == n);
 919         if (last && free_of(last)) {
 920                 coalesce_backw(ml, last);
 921                 ml = last;
 922         }
 923         check_mallinks("create_chunk, phys. linked");
 924         return ml;
 925 }
 926
 927 private
 928 truncate(register mallink *ml, size_t size)
 929 {
 930         /*      The chunk ml is truncated.
 931                 The chunk at ml is split in two.
 932                 The remaining part is then freed.
 933         */
 934         register mallink *new = (mallink *)((char *)ml + size);
 935         register mallink *ph_next = phys_next_of(ml);
 936
 937         new_mallink(new);
 938         set_free(new, 1);
 939         set_phys_prev(new, ml);
 940         set_phys_next(new, ph_next);
 941         calc_checksum(new);
 942         if (! last_mallink(ml)) {
 943                 set_phys_prev(ph_next, new);
 944                 calc_checksum(ph_next);
 945                 if (free_of(ph_next)) coalesce_forw(new, ph_next);
 946         }
 947         else    ml_last = new;
 948         set_phys_next(ml, new);
 949         calc_checksum(ml);
 950
 951         started_working_on(new);
 952         link_free_chunk(new);
 953         stopped_working_on(new);
 954         check_mallinks("truncate");
 955 }
 956
 957 private
 958 combine_chunks(register mallink *ml1, register mallink *ml2)
 959 {
 960         /*      The chunks ml1 and ml2 are combined.
 961         */
 962         register mallink *ml3 = phys_next_of(ml2);
 963
 964         set_phys_next(ml1, ml3);
 965         calc_checksum(ml1);
 966         if (!last_mallink(ml2)) {
 967                 set_phys_prev(ml3, ml1);
 968                 calc_checksum(ml3);
 969         }
 970         if (ml_last == ml2)
 971                 ml_last = ml1;
 972 }
 973
 974
 975 /**********************************************************/
 976 /*
 977 /*               This was file check.c
 978 /*
 979 /**********************************************************/
 980
 981 /* $Id: check.c,v 1.4 1994/06/24 11:55:12 ceriel Exp $ */
 982 /*
 983  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 984  * See the copyright notice in the ACK home directory, in the file "Copyright".
 985  */
 986 #include        <stdio.h>
 987
 988 #ifdef  CHECK                   /* otherwise this whole file is skipped */
 989
 990 /* ??? check these later */
 991 private acquire_malout(void), check_ml_last(const char *s);
 992 private dump_all_mallinks(void), dump_free_list(int i);
 993 private dump_mallink(const char *s, mallink *ml), print_loop(mallink *ml);
 994 private working_on(mallink *ml);
 995 private size_type checksum(mallink *ml);
 996 static FILE *malout;
 997
 998 private mallink *free_list_entry(int i);
 999
1000 #define for_free_list(i,p) \
1001         for (p = free_list_entry(i); p; p = log_next_of(p))
1002
1003 #define for_all_mallinks(ml)    /* backwards! */ \
1004         for (ml = ml_last; ml; \
1005                 ml = first_mallink(ml) ? MAL_NULL : phys_prev_of(ml))
1006
1007 /* Maldump */
1008
1009 static int pr_cnt = 0;
1010
1011 maldump(int n)  {
1012         /*      Dump pertinent info in pseudo-readable format;
1013                 abort afterwards if n != 0.
1014         */
1015         static int dumping = 0;
1016         int i;
1017
1018         if (dumping)
1019                 return;
1020         dumping++;
1021         acquire_malout();
1022         fprintf(malout,
1023                 ">>>>>>>>>>>>>>>> DUMP OF ALL MALLINKS <<<<<<<<<<<<<<<<");
1024         fprintf(malout, "    ml_last = %p\n", ml_last);
1025         if (++pr_cnt == 100) pr_cnt = 0;
1026         dump_all_mallinks();
1027         fprintf(malout,
1028                 ">>>>>>>>>>>>>>>> DUMP OF FREE_LISTS <<<<<<<<<<<<<<<<\n");
1029         if (++pr_cnt == 100) pr_cnt = 0;
1030         for (i = 0; i < MAX_FLIST; i++)
1031                 dump_free_list(i);
1032         fprintf(malout,
1033                 ">>>>>>>>>>>>>>>> END OF DUMP <<<<<<<<<<<<<<<<\n");
1034         fclose(malout);
1035         dumping--;
1036         if (n)
1037                 abort();
1038 }
1039
1040 private
1041 acquire_malout(void)    {
1042         static char buf[BUFSIZ];
1043
1044         if (!malout)    {
1045                 malout = freopen("mal.out", "w", stderr);
1046                 setbuf(malout, buf);
1047         }
1048 }
1049
1050 private
1051 dump_all_mallinks(void) {
1052         mallink *ml;
1053
1054         for_all_mallinks (ml)   {
1055                 if (print_loop(ml))
1056                         return;
1057                 dump_mallink((char *)0, ml);
1058         }
1059 }
1060
1061 private
1062 dump_free_list(int i)   {
1063         mallink *ml = free_list_entry(i);
1064
1065         if (!ml)
1066                 return;
1067         fprintf(malout, "%2d: ", i);
1068         for_free_list(i, ml)    {
1069                 if (print_loop(ml))
1070                         return;
1071                 fprintf(malout, "%p ", ml);
1072         }
1073         fprintf(malout, "<\n");
1074 }
1075
1076 private int
1077 print_loop(mallink *ml) {
1078         if (print_of(ml) == pr_cnt)     {
1079                 fprintf(malout, "... PRINT LOOP\n");
1080                 return 1;
1081         }
1082         set_print(ml, pr_cnt);
1083         return 0;
1084 }
1085
1086 private
1087 dump_mallink(const char *s, mallink *ml)        {
1088         acquire_malout();
1089         if (s)
1090                 fprintf(malout, "%s: ", s);
1091         fprintf(malout, "@: %p;", ml);
1092         if (ml && checksum_of(ml) != checksum(ml))
1093                 fprintf(malout, ">>>> CORRUPTED <<<<");
1094         if (!ml)        {
1095                 fprintf(malout, "\n");
1096                 return;
1097         }
1098         if (free_of(ml))        {
1099                 fprintf(malout, " l_p: %p;", _log_prev_of(ml));
1100                 fprintf(malout, " l_n: %p;", _log_next_of(ml));
1101         }
1102         fprintf(malout, " p_s: %p;", prev_size_of(ml));
1103         fprintf(malout, " t_s: %p;", _this_size_of(ml));
1104         fprintf(malout, " sz: %lu;", (unsigned long) size_of(ml));
1105         fprintf(malout, " fr: %d;", free_of(ml));
1106         fprintf(malout, "\n");
1107 }
1108
1109 /*      Check_mallinks() checks the total data structure as accessible
1110         through free_list[] and ml_last.  All check_sums should be OK,
1111         except those held in the small array off_colour.  This is a
1112         trick to allow to continue checking even when a few mallinks
1113         are temporarily out of order.
1114         Check_mallinks() tests for a lot of internal consistency.
1115 */
1116
1117 /* Some arbitrary constants */
1118 #define IN_ML_LAST      93
1119 #define IN_FREE_LIST    57              /* and in ml_last */
1120 #define CLEAR           21
1121
1122 #define VRIJ            1
1123 #define BEZET           2
1124
1125 private
1126 check_mallinks(const char *s)   {
1127         mallink *ml;
1128         size_type size;
1129         int i;
1130         char stat;
1131
1132         check_ml_last(s);
1133         stat = BEZET;
1134         for_all_mallinks(ml)    {
1135                 if (checksum_of(ml) != checksum(ml))
1136                         Error("mallink info at %p corrupted", s, ml);
1137                 if (working_on(ml))     {
1138                         stat = BEZET;
1139                         continue;
1140                 }
1141                 if (    !last_mallink(ml) &&
1142                         phys_prev_of(phys_next_of(ml)) != ml
1143                 )
1144                         Error("upward chain bad at %p", s, ml);
1145                 if (    !first_mallink(ml) &&
1146                         phys_next_of(phys_prev_of(ml)) != ml
1147                 )
1148                         Error("downward chain bad at %p", s, ml);
1149                 if (free_of(ml))        {
1150                         if (stat == VRIJ)
1151                                 Error("free mallink at %p follows free mallink",
1152                                                                 s, ml);
1153                         stat = VRIJ;
1154                 }
1155                 else
1156                         stat = BEZET;
1157                 set_mark(ml, IN_ML_LAST);
1158         }
1159
1160         for (i = 0, size = MIN_SIZE; i < MAX_FLIST; i++, size *= 2)     {
1161                 for_free_list(i, ml)    {
1162                         if (working_on(ml))
1163                                 continue;
1164                         if (!free_of(ml))
1165                                 Error("occupied mallink %p occurs in free_list", s, ml);
1166                         switch (mark_of(ml))    {
1167                         case IN_ML_LAST:
1168                                 set_mark(ml, IN_FREE_LIST);
1169                                 break;
1170                         case IN_FREE_LIST:
1171                                 Error("mallink %p occurs in 2 free_lists",
1172                                                                 s, ml);
1173                         default:
1174                                 Error("unknown mallink %p in free_list",
1175                                                                 s, ml);
1176                         }
1177                         if (size_of(ml) < size)
1178                                 Error("size of mallink %p too small", s, ml);
1179                         if (size_of(ml) >= 2*size)
1180                                 Error("size of mallink %p too large", s, ml);
1181                 }
1182         }
1183         for_all_mallinks (ml)   {
1184                 if (working_on(ml))
1185                         continue;
1186                 if (free_of(ml) && mark_of(ml) != IN_FREE_LIST)
1187                         Error("free mallink %p is in no free_list", s, ml);
1188                 set_mark(ml, CLEAR);
1189         }
1190 }
1191
1192 private
1193 check_ml_last(const char *s)    {
1194         if (ml_last && _this_size_of(ml_last) == 0)
1195                 Error("size of ml_last == 0, at %p", s, ml_last);
1196 }
1197
1198 private size_type
1199 checksum(mallink *ml)   {
1200         size_type sum = 0;
1201
1202         if (free_of(ml))        {
1203                 sum += (size_type)_log_prev_of(ml);
1204                 sum += (size_type)_log_next_of(ml);
1205         }
1206         sum += (size_type)prev_size_of(ml);
1207         sum += (size_type)_this_size_of(ml);
1208         return sum;
1209 }
1210
1211 private
1212 calc_checksum(mallink *ml)      {
1213         set_checksum(ml, checksum(ml));
1214 }
1215
1216 #define N_COLOUR        10
1217 static mallink *off_colour[N_COLOUR];
1218
1219 private
1220 started_working_on(mallink *ml) {
1221         int i;
1222
1223         for (i = 0; i < N_COLOUR; i++)
1224                 if (off_colour[i] == MAL_NULL)  {
1225                         off_colour[i] = ml;
1226                         return;
1227                 }
1228         Error("out of off_colour array at %p", "started_working_on", ml);
1229 }
1230
1231 private
1232 stopped_working_on(mallink *ml) {
1233         int i;
1234
1235         for (i = 0; i < N_COLOUR; i++)
1236                 if (off_colour[i] == ml)        {
1237                         off_colour[i] = MAL_NULL;
1238                         return;
1239                 }
1240         Error("stopped working on mallink %p", "stopped_working_on", ml);
1241 }
1242
1243 private int
1244 working_on(mallink *ml) {
1245         int i;
1246
1247         for (i = 0; i < N_COLOUR; i++)
1248                 if (off_colour[i] == ml)
1249                         return 1;
1250         return 0;
1251 }
1252
1253 private
1254 check_work_empty(const char *s) {
1255         int i;
1256         int cnt = 0;
1257
1258         for (i = 0; i < N_COLOUR; i++)
1259                 if (off_colour[i] != MAL_NULL)
1260                         cnt++;
1261         if (cnt != 0)
1262                 Error("off_colour not empty", s, MAL_NULL);
1263 }
1264
1265 private int
1266 Error(const char *fmt, const char *s, mallink *ml)      {
1267         static int already_called = 0;
1268
1269         if (already_called++) return 0;
1270         setbuf(stdout, (char *) 0);
1271         printf("%s: ", s);
1272         printf(fmt, (long)ml);
1273         printf("\n");
1274         acquire_malout();
1275         fprintf(malout, "%s: ", s);
1276         fprintf(malout, fmt, (long)ml);
1277         fprintf(malout, "\n");
1278         fflush(stdout);
1279         maldump(1);
1280         return 0;                       /* to satisfy lint */
1281 }
1282
1283 #endif  /* CHECK */
1284