home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / unix / programm / 3825 < prev    next >
Encoding:
Text File  |  1992-07-21  |  4.4 KB  |  99 lines
  1. Newsgroups: comp.unix.programmer
  2. Path: sparky!uunet!cs.utexas.edu!sdd.hp.com!think.com!paperboy.osf.org!meissner
  3. From: meissner@osf.org (Michael Meissner)
  4. Subject: Re: Duplication of malloc() definition
  5. In-Reply-To: darcy@druid.uucp's message of 18 Jul 92 00:24:07 GMT
  6. Message-ID: <MEISSNER.92Jul21113857@tiktok.osf.org>
  7. Sender: news@osf.org (USENET News System)
  8. Organization: Open Software Foundation
  9. References: <3800@moscom.UUCP> <1992Jul18.002407.20753@druid.uucp>
  10. Date: 21 Jul 92 11:38:57
  11. Lines: 86
  12.  
  13. In article <1992Jul18.002407.20753@druid.uucp> darcy@druid.uucp (D'Arcy J.M. Cain) writes:
  14.  
  15. | jmp@moscom.UUCP (Joe Palumbos) writes:
  16. | >Can someone tell me why the memmory allocation routines are
  17. | >defined in both malloc.h and in stdlib.h?  (i.e.: malloc(),
  18. | 
  19. | Because some older compilers used malloc.h and so for compatibility with
  20. | programs which use it malloc.h is included.  ANSI puts these functions
  21. | in stdlib.h and this is the right header to use.
  22.  
  23. Actually, it is not the compiler per se, but the operating system.
  24. Specifically, the early System V.x strain have two malloc's, one in
  25. libc.a, and the other in libmalloc.a (I dunno about V.4).  I can't
  26. remember exactly which System V.x release released libmalloc.a, but I
  27. have V.2 on-line, and it has it.  The header file malloc.h defines the
  28. interface to the routines in libmalloc.a, and adds a structure
  29. mallinfo, a function mallinfo (which returns a pointer to the mallinfo
  30. structure), and a function mallopt (which allows you to control the
  31. malloc algortihms).
  32.  
  33. The libc.a malloc was the original V7 malloc, and the libmalloc.a
  34. malloc was generally much faster than the V7 malloc, but used a little
  35. more memory by default.  It also did not preserve the V7 semantics
  36. that the data in freed blocks was untouched until the block was
  37. reallocated (awk and bc being the biggest two offenders if I remember
  38. correctly).
  39.  
  40. Here is the initial comment from the V.2 libmalloc malloc.c:
  41.  
  42. /*     use level memory allocater (malloc, free, realloc)
  43.  
  44.     -malloc, free, realloc and mallopt form a memory allocator
  45.     similar to malloc, free, and realloc.  The routines
  46.     here are much faster than the original, with slightly worse
  47.     space usage (a few percent difference on most input).  They
  48.     do not have the property that data in freed blocks is left
  49.     untouched until the space is reallocated.
  50.  
  51.     -Memory is kept in the "arena", a singly linked list of blocks.
  52.     These blocks are of 3 types.
  53.         1. A free block.  This is a block not in use by the
  54.            user.  It has a 3 word header. (See description
  55.            of the free queue.)
  56.         2. An allocated block.  This is a block the user has
  57.            requested.  It has only a 1 word header, pointing
  58.            to the next block of any sort.
  59.         3. A permanently allocated block.  This covers space
  60.            aquired by the user directly through sbrk().  It
  61.            has a 1 word header, as does 2.
  62.     Blocks of type 1 have the lower bit of the pointer to the
  63.     nextblock = 0.  Blocks of type 2 and 3 have that bit set,
  64.     to mark them busy.
  65.  
  66.     -Unallocated blocks are kept on an unsorted doubly linked
  67.     free list.  
  68.  
  69.     -Memory is allocated in blocks, with sizes specified by the
  70.     user.  A circular first-fit startegy is used, with a roving
  71.     head of the free queue, which prevents bunching of small
  72.     blocks at the head of the queue.
  73.  
  74.     -Compaction is performed at free time of any blocks immediately
  75.     following the freed block.  The freed block will be combined
  76.     with a preceding block during the search phase of malloc.
  77.     Since a freed block is added at the front of the free queue,
  78.     which is moved to the end of the queue if considered and
  79.     rejected during the search, fragmentation only occurs if
  80.     a block with a contiguious preceding block that is free is
  81.     freed and reallocated on the next call to malloc.  The
  82.     time savings of this strategy is judged to be worth the
  83.     occasional waste of memory.
  84.  
  85.     -Small blocks (of size < MAXSIZE)  are not allocated directly.
  86.     A large "holding" block is allocated via a recursive call to
  87.     malloc.  This block contains a header and ?????? small blocks.
  88.     Holding blocks for a given size of small block (rounded to the
  89.     nearest ALIGNSZ bytes) are kept on a queue with the property that any
  90.     holding block with an unused small block is in front of any without.
  91.     A list of free blocks is kept within the holding block.
  92. */
  93.  
  94. --
  95. Michael Meissner    email: meissner@osf.org        phone: 617-621-8861
  96. Open Software Foundation, 11 Cambridge Center, Cambridge, MA, 02142
  97.  
  98. You are in a twisty little passage of standards, all conflicting.
  99.