source: trunk/minix/commands/ash/test/malloc.c@ 15

Last change on this file since 15 was 9, checked in by Mattia Monga, 14 years ago

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