0a0d50698df347219272e395a8b86944597b6fcc
[akaros.git] / user / electric-fence / efence.c
1 /*
2  * Electric Fence - Red-Zone memory allocator.
3  * Bruce Perens, 1988, 1993
4  * 
5  * For email below, drop spaces and <spam-buster> tag.
6  * MODIFIED:  March 20, 2014 (jric<spam-buster> @ <spam-buster> chegg DOT com)
7  *
8  * This is a special version of malloc() and company for debugging software
9  * that is suspected of overrunning or underrunning the boundaries of a
10  * malloc buffer, or touching free memory.
11  *
12  * It arranges for each malloc buffer to be followed (or preceded)
13  * in the address space by an inaccessable virtual memory page,
14  * and for free memory to be inaccessable. If software touches the
15  * inaccessable page, it will get an immediate segmentation
16  * fault. It is then trivial to uncover the offending code using a debugger.
17  *
18  * An advantage of this product over most malloc debuggers is that this one
19  * detects reading out of bounds as well as writing, and this one stops on
20  * the exact instruction that causes the error, rather than waiting until the
21  * next boundary check.
22  *
23  * There is one product that debugs malloc buffer overruns
24  * better than Electric Fence: "Purify" from Purify Systems, and that's only
25  * a small part of what Purify does. I'm not affiliated with Purify, I just
26  * respect a job well done.
27  *
28  * This version of malloc() should not be linked into production software,
29  * since it tremendously increases the time and memory overhead of malloc().
30  * Each malloc buffer will consume a minimum of two virtual memory pages,
31  * this is 16 kilobytes on many systems. On some systems it will be necessary
32  * to increase the amount of swap space in order to debug large programs that
33  * perform lots of allocation, because of the per-buffer overhead.
34  *
35  */
36 #include "efence.h"
37 #include <stdlib.h>
38 #include <unistd.h>
39 #include <memory.h>
40 #include <string.h>
41 #include <pthread.h>
42 #include <errno.h>
43
44 #ifdef  malloc
45 #undef  malloc
46 #endif
47
48 #ifdef  calloc
49 #undef  calloc
50 #endif
51
52 static const char       version[] = "\n  Electric Fence 2.2"
53  " Copyright (C) 1987-2014 Bruce Perens.\n";
54
55 /*
56  * MEMORY_CREATION_SIZE is the amount of memory to get from the operating
57  * system at one time. We'll break that memory down into smaller pieces for
58  * malloc buffers. One megabyte is probably a good value.
59  */
60 #define                 MEMORY_CREATION_SIZE    1024 * 1024
61
62 /*
63  * Enum Mode indicates the status of a malloc buffer.
64  */
65 enum _Mode {
66         NOT_IN_USE = 0, /* Available to represent a malloc buffer. */
67         FREE,           /* A free buffer. */
68         ALLOCATED,      /* A buffer that is in use. */
69         PROTECTED,      /* A freed buffer that can not be allocated again. */
70         INTERNAL_USE    /* A buffer used internally by malloc(). */
71 };
72 typedef enum _Mode      Mode;
73
74 /*
75  * Struct Slot contains all of the information about a malloc buffer except
76  * for the contents of its memory.
77  */
78 struct _Slot {
79         void *          userAddress;
80         void *          internalAddress;
81         size_t          userSize;
82         size_t          internalSize;
83         Mode            mode;
84 };
85 typedef struct _Slot    Slot;
86
87  /*
88  * EF_DISABLE_BANNER is a global variable used to control whether
89  * Electric Fence prints its usual startup message.  If the value is
90  * -1, it will be set from the environment default to 0 at run time.
91  */
92 int            EF_DISABLE_BANNER = -1;
93
94
95 /*
96  * EF_ALIGNMENT is a global variable used to control the default alignment
97  * of buffers returned by malloc(), calloc(), and realloc(). It is all-caps
98  * so that its name matches the name of the environment variable that is used
99  * to set it. This gives the programmer one less name to remember.
100  * If the value is -1, it will be set from the environment or sizeof(int)
101  * at run time.
102  */
103 int             EF_ALIGNMENT = -1;
104
105 /*
106  * EF_PROTECT_FREE is a global variable used to control the disposition of
107  * memory that is released using free(). It is all-caps so that its name
108  * matches the name of the environment variable that is used to set it.
109  * If its value is greater non-zero, memory released by free is made
110  * inaccessable and never allocated again. Any software that touches free
111  * memory will then get a segmentation fault. If its value is zero, freed
112  * memory will be available for reallocation, but will still be inaccessable
113  * until it is reallocated.
114  * If the value is -1, it will be set from the environment or to 0 at run-time.
115  */
116 int             EF_PROTECT_FREE = -1;
117
118 /*
119  * EF_PROTECT_BELOW is used to modify the behavior of the allocator. When
120  * its value is non-zero, the allocator will place an inaccessable page
121  * immediately _before_ the malloc buffer in the address space, instead
122  * of _after_ it. Use this to detect malloc buffer under-runs, rather than
123  * over-runs. It won't detect both at the same time, so you should test your
124  * software twice, once with this value clear, and once with it set.
125  * If the value is -1, it will be set from the environment or to zero at
126  * run-time
127  */
128 int             EF_PROTECT_BELOW = -1;
129
130 /*
131  * EF_ALLOW_MALLOC_0 is set if Electric Fence is to allow malloc(0). I
132  * trap malloc(0) by default because it is a common source of bugs.
133  */
134 int             EF_ALLOW_MALLOC_0 = -1;
135
136 /*
137  * EF_FREE_WIPES is set if Electric Fence is to wipe the memory content
138  * of freed blocks.  This makes it easier to check if memory is freed or
139  * not
140  */
141 int            EF_FREE_WIPES = -1;
142
143 /*
144  * allocationList points to the array of slot structures used to manage the
145  * malloc arena.
146  */
147 static Slot *           allocationList = 0;
148
149 /*
150  * allocationListSize is the size of the allocation list. This will always
151  * be a multiple of the page size.
152  */
153 static size_t           allocationListSize = 0;
154
155 /*
156  * slotCount is the number of Slot structures in allocationList.
157  */
158 static size_t           slotCount = 0;
159
160 /*
161  * unUsedSlots is the number of Slot structures that are currently available
162  * to represent new malloc buffers. When this number gets too low, we will
163  * create new slots.
164  */
165 static size_t           unUsedSlots = 0;
166
167 /*
168  * slotsPerPage is the number of slot structures that fit in a virtual
169  * memory page.
170  */
171 static size_t           slotsPerPage = 0;
172
173 /*
174  * internalUse is set when allocating and freeing the allocatior-internal
175  * data structures.
176  */
177 static int              internalUse = 0;
178
179 /*
180  * noAllocationListProtection is set to tell malloc() and free() not to
181  * manipulate the protection of the allocation list. This is only set in
182  * realloc(), which does it to save on slow system calls, and in
183  * allocateMoreSlots(), which does it because it changes the allocation list.
184  */
185 static int              noAllocationListProtection = 0;
186
187 /*
188  * bytesPerPage is set at run-time to the number of bytes per virtual-memory
189  * page, as returned by Page_Size().
190  */
191 static size_t           bytesPerPage = 0;
192
193  /*
194  * mutex to enable multithreaded operation
195  */
196 static pthread_mutex_t mutex ;
197 static pid_t mutexpid=0;
198 static int locknr=0;
199
200
201 static void lock() {
202     if (pthread_mutex_trylock(&mutex)) {
203        if (mutexpid==getpid()) {
204            locknr++;
205            return;
206        } else {
207            pthread_mutex_lock(&mutex);
208        }
209     } 
210     mutexpid=getpid();
211     locknr=1;
212 }
213
214 static void unlock() {
215     locknr--;
216     if (!locknr) {
217        mutexpid=0;
218        pthread_mutex_unlock(&mutex);
219     }
220 }
221
222 /*
223  * internalError is called for those "shouldn't happen" errors in the
224  * allocator.
225  */
226 static void
227 internalError(void)
228 {
229         EF_Abort("Internal error in allocator.");
230 }
231
232 /*
233  * initialize sets up the memory allocation arena and the run-time
234  * configuration information.
235  */
236 static void
237 initialize(void)
238 {
239         size_t  size = MEMORY_CREATION_SIZE;
240         size_t  slack;
241         char *  string;
242         Slot *  slot;
243
244        if ( EF_DISABLE_BANNER == -1 ) {
245                if ( (string = getenv("EF_DISABLE_BANNER")) != 0 )
246                        EF_DISABLE_BANNER = atoi(string);
247                else
248                        EF_DISABLE_BANNER = 0;
249        }
250
251        if ( EF_DISABLE_BANNER == 0 )
252                EF_Print(version);
253
254         /*
255          * Import the user's environment specification of the default
256          * alignment for malloc(). We want that alignment to be under
257          * user control, since smaller alignment lets us catch more bugs,
258          * however some software will break if malloc() returns a buffer
259          * that is not word-aligned.
260          *
261          * I would like
262          * alignment to be zero so that we could catch all one-byte
263          * overruns, however if malloc() is asked to allocate an odd-size
264          * buffer and returns an address that is not word-aligned, or whose
265          * size is not a multiple of the word size, software breaks.
266          * This was the case with the Sun string-handling routines,
267          * which can do word fetches up to three bytes beyond the end of a
268          * string. I handle this problem in part by providing
269          * byte-reference-only versions of the string library functions, but
270          * there are other functions that break, too. Some in X Windows, one
271          * in Sam Leffler's TIFF library, and doubtless many others.
272          */
273         if ( EF_ALIGNMENT == -1 ) {
274                 if ( (string = getenv("EF_ALIGNMENT")) != 0 )
275                         EF_ALIGNMENT = (size_t)atoi(string);
276                 else
277                         EF_ALIGNMENT = sizeof(int);
278         }
279
280         /*
281          * See if the user wants to protect the address space below a buffer,
282          * rather than that above a buffer.
283          */
284         if ( EF_PROTECT_BELOW == -1 ) {
285                 if ( (string = getenv("EF_PROTECT_BELOW")) != 0 )
286                         EF_PROTECT_BELOW = (atoi(string) != 0);
287                 else
288                         EF_PROTECT_BELOW = 0;
289         }
290
291         /*
292          * See if the user wants to protect memory that has been freed until
293          * the program exits, rather than until it is re-allocated.
294          */
295         if ( EF_PROTECT_FREE == -1 ) {
296                 if ( (string = getenv("EF_PROTECT_FREE")) != 0 )
297                         EF_PROTECT_FREE = (atoi(string) != 0);
298                 else
299                         EF_PROTECT_FREE = 0;
300         }
301
302         /*
303          * See if the user wants to allow malloc(0).
304          */
305         if ( EF_ALLOW_MALLOC_0 == -1 ) {
306                 if ( (string = getenv("EF_ALLOW_MALLOC_0")) != 0 )
307                         EF_ALLOW_MALLOC_0 = (atoi(string) != 0);
308                 else
309                         EF_ALLOW_MALLOC_0 = 0;
310         }
311
312         /*
313          * See if the user wants us to wipe out freed memory.
314          */
315         if ( EF_FREE_WIPES == -1 ) {
316                 if ( (string = getenv("EF_FREE_WIPES")) != 0 )
317                         EF_FREE_WIPES = (atoi(string) != 0);
318                 else
319                         EF_FREE_WIPES = 0;
320         }
321
322         /*
323          * Get the run-time configuration of the virtual memory page size.
324          */
325         bytesPerPage = Page_Size();
326
327         /*
328          * Figure out how many Slot structures to allocate at one time.
329          */
330         slotCount = slotsPerPage = bytesPerPage / sizeof(Slot);
331         allocationListSize = bytesPerPage;
332
333         if ( allocationListSize > size )
334                 size = allocationListSize;
335
336         if ( (slack = size % bytesPerPage) != 0 )
337                 size += bytesPerPage - slack;
338
339         /*
340          * Allocate memory, and break it up into two malloc buffers. The
341          * first buffer will be used for Slot structures, the second will
342          * be marked free.
343          */
344         slot = allocationList = (Slot *)Page_Create(size);
345         memset((char *)allocationList, 0, allocationListSize);
346
347         slot[0].internalSize = slot[0].userSize = allocationListSize;
348         slot[0].internalAddress = slot[0].userAddress = allocationList;
349         slot[0].mode = INTERNAL_USE;
350         if ( size > allocationListSize ) {
351                 slot[1].internalAddress = slot[1].userAddress
352                  = ((char *)slot[0].internalAddress) + slot[0].internalSize;
353                 slot[1].internalSize
354                  = slot[1].userSize = size - slot[0].internalSize;
355                 slot[1].mode = FREE;
356         }
357
358         /*
359          * Deny access to the free page, so that we will detect any software
360          * that treads upon free memory.
361          */
362         Page_DenyAccess(slot[1].internalAddress, slot[1].internalSize);
363
364         /*
365          * Account for the two slot structures that we've used.
366          */
367         unUsedSlots = slotCount - 2;
368 }
369
370 /*
371  * allocateMoreSlots is called when there are only enough slot structures
372  * left to support the allocation of a single malloc buffer.
373  */
374 static void
375 allocateMoreSlots(void)
376 {
377         size_t  newSize = allocationListSize + bytesPerPage;
378         void *  newAllocation;
379         void *  oldAllocation = allocationList;
380
381         Page_AllowAccess(allocationList, allocationListSize);
382         noAllocationListProtection = 1;
383         internalUse = 1;
384
385         newAllocation = malloc(newSize);
386         memcpy(newAllocation, allocationList, allocationListSize);
387         memset(&(((char *)newAllocation)[allocationListSize]), 0, bytesPerPage);
388
389         allocationList = (Slot *)newAllocation;
390         allocationListSize = newSize;
391         slotCount += slotsPerPage;
392         unUsedSlots += slotsPerPage;
393
394         free(oldAllocation);
395
396         /*
397          * Keep access to the allocation list open at this point, because
398          * I am returning to memalign(), which needs that access.
399          */
400         noAllocationListProtection = 0;
401         internalUse = 0;
402 }
403
404 /*
405  * This is the memory allocator. When asked to allocate a buffer, allocate
406  * it in such a way that the end of the buffer is followed by an inaccessable
407  * memory page. If software overruns that buffer, it will touch the bad page
408  * and get an immediate segmentation fault. It's then easy to zero in on the
409  * offending code with a debugger.
410  *
411  * There are a few complications. If the user asks for an odd-sized buffer,
412  * we would have to have that buffer start on an odd address if the byte after
413  * the end of the buffer was to be on the inaccessable page. Unfortunately,
414  * there is lots of software that asks for odd-sized buffers and then
415  * requires that the returned address be word-aligned, or the size of the
416  * buffer be a multiple of the word size. An example are the string-processing
417  * functions on Sun systems, which do word references to the string memory
418  * and may refer to memory up to three bytes beyond the end of the string.
419  * For this reason, I take the alignment requests to memalign() and valloc()
420  * seriously, and 
421  * 
422  * Electric Fence wastes lots of memory. I do a best-fit allocator here
423  * so that it won't waste even more. It's slow, but thrashing because your
424  * working set is too big for a system's RAM is even slower. 
425  */
426 extern C_LINKAGE void *
427 memalign(size_t alignment, size_t userSize)
428 {
429         register Slot * slot;
430         register size_t count;
431         Slot *          fullSlot = 0;
432         Slot *          emptySlots[2];
433         size_t          internalSize;
434         size_t          slack;
435         char *          address;
436
437         if ( allocationList == 0 )
438                 initialize();
439
440         if ( userSize == 0 && !EF_ALLOW_MALLOC_0 )
441                 EF_Abort("Allocating 0 bytes, probably a bug.");
442
443         /*
444          * If EF_PROTECT_BELOW is set, all addresses returned by malloc()
445          * and company will be page-aligned.
446          */
447         if ( !EF_PROTECT_BELOW && alignment > 1 ) {
448                 if ( (slack = userSize % alignment) != 0 )
449                         userSize += alignment - slack;
450         }
451
452         /*
453          * The internal size of the buffer is rounded up to the next page-size
454          * boudary, and then we add another page's worth of memory for the
455          * dead page.
456          */
457         internalSize = userSize + bytesPerPage;
458         if ( (slack = internalSize % bytesPerPage) != 0 )
459                 internalSize += bytesPerPage - slack;
460
461         /*
462          * These will hold the addresses of two empty Slot structures, that
463          * can be used to hold information for any memory I create, and any
464          * memory that I mark free.
465          */
466         emptySlots[0] = 0;
467         emptySlots[1] = 0;
468
469         /*
470          * The internal memory used by the allocator is currently
471          * inaccessable, so that errant programs won't scrawl on the
472          * allocator's arena. I'll un-protect it here so that I can make
473          * a new allocation. I'll re-protect it before I return.
474          */
475         if ( !noAllocationListProtection )
476                 Page_AllowAccess(allocationList, allocationListSize);
477
478         /*
479          * If I'm running out of empty slots, create some more before
480          * I don't have enough slots left to make an allocation.
481          */
482         if ( !internalUse && unUsedSlots < 7 ) {
483                 allocateMoreSlots();
484         }
485         
486         /*
487          * Iterate through all of the slot structures. Attempt to find a slot
488          * containing free memory of the exact right size. Accept a slot with
489          * more memory than we want, if the exact right size is not available.
490          * Find two slot structures that are not in use. We will need one if
491          * we split a buffer into free and allocated parts, and the second if
492          * we have to create new memory and mark it as free.
493          *
494          */
495         
496         for ( slot = allocationList, count = slotCount ; count > 0; count-- ) {
497                 if ( slot->mode == FREE
498                  && slot->internalSize >= internalSize ) {
499                         if ( !fullSlot
500                          ||slot->internalSize < fullSlot->internalSize){
501                                 fullSlot = slot;
502                                 if ( slot->internalSize == internalSize
503                                  && emptySlots[0] )
504                                         break;  /* All done, */
505                         }
506                 }
507                 else if ( slot->mode == NOT_IN_USE ) {
508                         if ( !emptySlots[0] )
509                                 emptySlots[0] = slot;
510                         else if ( !emptySlots[1] )
511                                 emptySlots[1] = slot;
512                         else if ( fullSlot
513                          && fullSlot->internalSize == internalSize )
514                                 break;  /* All done. */
515                 }
516                 slot++;
517         }
518         if ( !emptySlots[0] )
519                 internalError();
520
521         if ( !fullSlot ) {
522                 /*
523                  * I get here if I haven't been able to find a free buffer
524                  * with all of the memory I need. I'll have to create more
525                  * memory. I'll mark it all as free, and then split it into
526                  * free and allocated portions later.
527                  */
528                 size_t  chunkSize = MEMORY_CREATION_SIZE;
529
530                 if ( !emptySlots[1] )
531                         internalError();
532
533                 if ( chunkSize < internalSize )
534                         chunkSize = internalSize;
535
536                 if ( (slack = chunkSize % bytesPerPage) != 0 )
537                         chunkSize += bytesPerPage - slack;
538
539                 /* Use up one of the empty slots to make the full slot. */
540                 fullSlot = emptySlots[0];
541                 emptySlots[0] = emptySlots[1];
542                 fullSlot->internalAddress = Page_Create(chunkSize);
543                 fullSlot->internalSize = chunkSize;
544                 fullSlot->mode = FREE;
545                 unUsedSlots--;
546         }
547
548         /*
549          * If I'm allocating memory for the allocator's own data structures,
550          * mark it INTERNAL_USE so that no errant software will be able to
551          * free it.
552          */
553         if ( internalUse )
554                 fullSlot->mode = INTERNAL_USE;
555         else
556                 fullSlot->mode = ALLOCATED;
557
558         /*
559          * If the buffer I've found is larger than I need, split it into
560          * an allocated buffer with the exact amount of memory I need, and
561          * a free buffer containing the surplus memory.
562          */
563         if ( fullSlot->internalSize > internalSize ) {
564                 emptySlots[0]->internalSize
565                  = fullSlot->internalSize - internalSize;
566                 emptySlots[0]->internalAddress
567                  = ((char *)fullSlot->internalAddress) + internalSize;
568                 emptySlots[0]->mode = FREE;
569                 fullSlot->internalSize = internalSize;
570                 unUsedSlots--;
571         }
572
573         if ( !EF_PROTECT_BELOW ) {
574                 /*
575                  * Arrange the buffer so that it is followed by an inaccessable
576                  * memory page. A buffer overrun that touches that page will
577                  * cause a segmentation fault.
578                  */
579                 address = (char *)fullSlot->internalAddress;
580
581                 /* Set up the "live" page. */
582                 if ( internalSize - bytesPerPage > 0 )
583                                 Page_AllowAccess(
584                                  fullSlot->internalAddress
585                                 ,internalSize - bytesPerPage);
586                         
587                 address += internalSize - bytesPerPage;
588
589                 /* Set up the "dead" page. */
590                 Page_DenyAccess(address, bytesPerPage);
591
592                 /* Figure out what address to give the user. */
593                 address -= userSize;
594         }
595         else {  /* EF_PROTECT_BELOW != 0 */
596                 /*
597                  * Arrange the buffer so that it is preceded by an inaccessable
598                  * memory page. A buffer underrun that touches that page will
599                  * cause a segmentation fault.
600                  */
601                 address = (char *)fullSlot->internalAddress;
602
603                 /* Set up the "dead" page. */
604                 Page_DenyAccess(address, bytesPerPage);
605                         
606                 address += bytesPerPage;
607
608                 /* Set up the "live" page. */
609                 if ( internalSize - bytesPerPage > 0 )
610                         Page_AllowAccess(address, internalSize - bytesPerPage);
611         }
612
613         fullSlot->userAddress = address;
614         fullSlot->userSize = userSize;
615
616         /*
617          * Make the pool's internal memory inaccessable, so that the program
618          * being debugged can't stomp on it.
619          */
620         if ( !internalUse )
621                 Page_DenyAccess(allocationList, allocationListSize);
622
623         return address;
624 }
625
626 /*
627  * Find the slot structure for a user address.
628  */
629 static Slot *
630 slotForUserAddress(void * address)
631 {
632         register Slot * slot = allocationList;
633         register size_t count = slotCount;
634         
635         for ( ; count > 0; count-- ) {
636                 if ( slot->userAddress == address )
637                         return slot;
638                 slot++;
639         }
640
641         return 0;
642 }
643
644 /*
645  * Find the slot structure for an internal address.
646  */
647 static Slot *
648 slotForInternalAddress(void * address)
649 {
650         register Slot * slot = allocationList;
651         register size_t count = slotCount;
652         
653         for ( ; count > 0; count-- ) {
654                 if ( slot->internalAddress == address )
655                         return slot;
656                 slot++;
657         }
658         return 0;
659 }
660
661 /*
662  * Given the internal address of a buffer, find the buffer immediately
663  * before that buffer in the address space. This is used by free() to
664  * coalesce two free buffers into one.
665  */
666 static Slot *
667 slotForInternalAddressPreviousTo(void * address)
668 {
669         register Slot * slot = allocationList;
670         register size_t count = slotCount;
671         
672         for ( ; count > 0; count-- ) {
673                 if ( ((char *)slot->internalAddress)
674                  + slot->internalSize == address )
675                         return slot;
676                 slot++;
677         }
678         return 0;
679 }
680
681 extern C_LINKAGE void
682 free(void * address)
683 {
684         Slot *  slot;
685         Slot *  previousSlot = 0;
686         Slot *  nextSlot = 0;
687
688         lock();
689
690         if ( address == 0 ) {
691                 unlock();
692                 return;
693         }
694
695         if ( allocationList == 0 )
696                 EF_Abort("free() called before first malloc().");
697
698         if ( !noAllocationListProtection )
699                 Page_AllowAccess(allocationList, allocationListSize);
700
701         slot = slotForUserAddress(address);
702
703         if ( !slot )
704                 EF_Abort("free(%a): address not from malloc().", address);
705
706         if ( slot->mode != ALLOCATED ) {
707                 if ( internalUse && slot->mode == INTERNAL_USE )
708                         /* Do nothing. */;
709                 else {
710                         EF_Abort(
711                          "free(%a): freeing free memory."
712                         ,address);
713                 }
714         }
715
716         if ( EF_PROTECT_FREE )
717                 slot->mode = PROTECTED;
718         else
719                 slot->mode = FREE;
720
721        if ( EF_FREE_WIPES )
722                memset(slot->userAddress, 0xbd, slot->userSize);
723
724         previousSlot = slotForInternalAddressPreviousTo(slot->internalAddress);
725         nextSlot = slotForInternalAddress(
726          ((char *)slot->internalAddress) + slot->internalSize);
727
728         if ( previousSlot
729          && (previousSlot->mode == FREE || previousSlot->mode == PROTECTED) ) {
730                 /* Coalesce previous slot with this one. */
731                 previousSlot->internalSize += slot->internalSize;
732                 if ( EF_PROTECT_FREE )
733                         previousSlot->mode = PROTECTED;
734
735                 slot->internalAddress = slot->userAddress = 0;
736                 slot->internalSize = slot->userSize = 0;
737                 slot->mode = NOT_IN_USE;
738                 slot = previousSlot;
739                 unUsedSlots++;
740         }
741         if ( nextSlot
742          && (nextSlot->mode == FREE || nextSlot->mode == PROTECTED) ) {
743                 /* Coalesce next slot with this one. */
744                 slot->internalSize += nextSlot->internalSize;
745                 nextSlot->internalAddress = nextSlot->userAddress = 0;
746                 nextSlot->internalSize = nextSlot->userSize = 0;
747                 nextSlot->mode = NOT_IN_USE;
748                 unUsedSlots++;
749         }
750
751         slot->userAddress = slot->internalAddress;
752         slot->userSize = slot->internalSize;
753
754         /*
755          * Free memory is _always_ set to deny access. When EF_PROTECT_FREE
756          * is true, free memory is never reallocated, so it remains access
757          * denied for the life of the process. When EF_PROTECT_FREE is false, 
758          * the memory may be re-allocated, at which time access to it will be
759          * allowed again.
760          */
761         Page_DenyAccess(slot->internalAddress, slot->internalSize);
762
763         if ( !noAllocationListProtection )
764                 Page_DenyAccess(allocationList, allocationListSize);
765
766         unlock();
767 }
768
769 extern C_LINKAGE void *
770 realloc(void * oldBuffer, size_t newSize)
771 {
772         void *  newBuffer = malloc(newSize);
773
774         lock();
775
776         if ( oldBuffer ) {
777                 size_t  size;
778                 Slot *  slot;
779
780                 Page_AllowAccess(allocationList, allocationListSize);
781                 noAllocationListProtection = 1;
782                 
783                 slot = slotForUserAddress(oldBuffer);
784
785                 if ( slot == 0 )
786                         EF_Abort(
787                          "realloc(%a, %d): address not from malloc()."
788                         ,oldBuffer
789                         ,newSize);
790
791                 if ( newSize < (size = slot->userSize) )
792                         size = newSize;
793
794                 if ( size > 0 )
795                         memcpy(newBuffer, oldBuffer, size);
796
797                 free(oldBuffer);
798                 noAllocationListProtection = 0;
799                 Page_DenyAccess(allocationList, allocationListSize);
800
801                 if ( size < newSize )
802                         memset(&(((char *)newBuffer)[size]), 0, newSize - size);
803                 
804                 /* Internal memory was re-protected in free() */
805         }
806         unlock();
807
808         return newBuffer;
809 }
810
811 extern C_LINKAGE void *
812 malloc(size_t size)
813 {
814         void  *allocation;   
815  
816         if ( allocationList == 0 ) {
817                 pthread_mutex_init(&mutex, NULL); 
818                 initialize();   /* This sets EF_ALIGNMENT */
819         }       
820         lock();
821         allocation=memalign(EF_ALIGNMENT, size); 
822
823         unlock();
824
825         return allocation;
826 }
827
828 extern C_LINKAGE char *
829 strdup(const char *s1)
830 {
831         if (!s1) return 0;
832         char *s2 = malloc(strlen(s1) + 1);
833
834         if (!s2) {
835                 errno = ENOMEM;
836                 return 0;
837         }
838
839         return strcpy(s2, s1);
840 }
841
842 extern C_LINKAGE char *
843 strndup(const char *s1, size_t n)
844 {
845         if (!s1) return 0;
846         int complete_size = n;  /* includes terminating null */
847         for (int i = 0; i < n - 1; i++) {
848                 if (!s1[i]) {
849                         complete_size = i + 2;
850                         break;
851                 }
852         }
853         char *s2 = malloc(complete_size);
854
855         if (!s2) {
856                 errno = ENOMEM;
857                 return 0;
858         }
859
860         strncpy(s2, s1, complete_size - 1);
861         s2[complete_size - 1] = '\0';
862
863         return s2;
864 }
865
866 extern C_LINKAGE void *
867 calloc(size_t nelem, size_t elsize)
868 {
869         size_t  size = nelem * elsize;
870         void * allocation;
871         
872         lock();
873        
874         allocation = malloc(size);
875         memset(allocation, 0, size);
876         unlock();
877
878         return allocation;
879 }
880
881 /*
882  * This will catch more bugs if you remove the page alignment, but it
883  * will break some software.
884  */
885 extern C_LINKAGE void *
886 valloc (size_t size)
887 {
888         void * allocation;
889        
890         lock();
891         allocation= memalign(bytesPerPage, size);
892         unlock();
893        
894         return allocation;
895 }