home *** CD-ROM | disk | FTP | other *** search
/ The CDPD Public Domain Collection for CDTV 3 / CDPDIII.bin / pd / programming / gnuc / library / rcs / buddy-alloc.c,v < prev    next >
Encoding:
Text File  |  1992-09-14  |  15.9 KB  |  673 lines
  1. head    1.2;
  2. access;
  3. symbols
  4.     version39-41:1.1;
  5. locks;
  6. comment    @ *  @;
  7.  
  8.  
  9. 1.2
  10. date    92.09.14.01.40.24;    author mwild;    state Exp;
  11. branches;
  12. next    1.1;
  13.  
  14. 1.1
  15. date    92.05.22.01.42.33;    author mwild;    state Exp;
  16. branches;
  17. next    ;
  18.  
  19.  
  20. desc
  21. @buddy allocator, replaces AllocMem()/FreeMem() calls in [k]malloc.c
  22. @
  23.  
  24.  
  25. 1.2
  26. log
  27. @change from using aligned blocks (obtained thru an AllocMem/FreeMem/AllocAbs
  28. hack) to using non-aligned blocks. The price for this is an additional
  29. field in every allocated block.
  30.  
  31. In the same run, change Forbid/Permit into Semaphore locking.
  32. @
  33. text
  34. @/*
  35.  *  This file is part of ixemul.library for the Amiga.
  36.  *  Copyright (C) 1991, 1992  Markus M. Wild
  37.  *
  38.  *  This library is free software; you can redistribute it and/or
  39.  *  modify it under the terms of the GNU Library General Public
  40.  *  License as published by the Free Software Foundation; either
  41.  *  version 2 of the License, or (at your option) any later version.
  42.  *
  43.  *  This library is distributed in the hope that it will be useful,
  44.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  45.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  46.  *  Library General Public License for more details.
  47.  *
  48.  *  You should have received a copy of the GNU Library General Public
  49.  *  License along with this library; if not, write to the Free
  50.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  51.  *
  52.  *  $Id: buddy-alloc.c,v 1.1 1992/05/22 01:42:33 mwild Exp $
  53.  *
  54.  *  $Log: buddy-alloc.c,v $
  55.  *  Revision 1.1  1992/05/22  01:42:33  mwild
  56.  *  Initial revision
  57.  *
  58.  */
  59. #define KERNEL
  60. #include "ixemul.h"
  61. #include <exec/memory.h>
  62. #include <stddef.h>
  63.  
  64. #undef DEBUG
  65.  
  66. #ifdef TEST
  67. #ifndef PRETTY_STABLE
  68. #define AllocMem(size,attr)    test_allocmem(size,attr)
  69. #define AllocAbs(size,buf)    test_allocabs(size,buf)
  70. #define FreeMem(buf,size)    test_freemem(buf,size)
  71. #define Forbid()
  72. #define Permit()
  73. #define ix_panic(str) puts(str)
  74. #define P(arg) printf arg
  75. #else
  76. #define P(arg)
  77. #define ix_panic(arg)
  78. #endif
  79. #else
  80. #ifdef DEBUG
  81. #define P(arg) kprintf arg
  82. #else
  83. #define P(arg)
  84. #endif
  85. #endif
  86.  
  87. /* this provides a straight replacement for AllocMem() and FreeMem().
  88.    Being this, it does *not* remember the size of allocation, the
  89.    clients have to do this instead. */
  90.  
  91. /* NOTE: currently only two pools are supported, MEMF_PUBLIC and
  92.          ! MEMF_PUBLIC. No MEMF_CHIP pools are needed by the library
  93.          and are thus not supported */
  94.  
  95.  
  96.  
  97.  
  98. /* TUNING: The two parameters that can be adjusted to fine tune
  99.            allocation strategy are MAXSIZE and BUDDY_LIMIT. By setting
  100.            MAXSIZE larger than BUDDY_LIMIT results in less Exec
  101.            overhead, since blocks stay longer in the buddy system.
  102.            Setting MAXSIZE==BUDDY_LIMIT sets memory usage to the
  103.            minimum, at the cost of more Exec calls. */
  104.  
  105.  
  106. /* no request for memory can be lower than this */
  107. #define MINLOG2        3
  108. #define MINSIZE        (1 << MINLOG2)
  109.  
  110. /* this is the size the buddy system gets memory pieces from Exec */
  111. #define MAXLOG2        15    /* get 32K chunks */
  112. #define MAXSIZE        (1 << MAXLOG2)
  113.  
  114. /* this is the limit for b_alloc to go straight to Exec */
  115. #define BUDDY_LIMIT    (1 << (MAXLOG2 - 5))    /* but serve only upto 1K */
  116.  
  117.  
  118.  
  119. #define PRIVATE_POOL    0
  120. #define PUBLIC_POOL    1
  121. #define NUMPOOLS    2    /* public and !public */
  122.  
  123. struct free_list {
  124.   u_int  exec_attr;
  125.   struct SignalSemaphore sem;
  126.   struct MinList buckets[MAXLOG2 - MINLOG2];
  127. } free_list[NUMPOOLS] = { { 0, }, { MEMF_PUBLIC, } };
  128.  
  129.  
  130. struct free_block {
  131.   /* if head is 0, the block is free, and index indicates its size */
  132.   struct free_list *head;
  133.   /* this is the price we pay for allowing non-aligned blocks. Each block
  134.      allocated with this buddy system has to carry the information along
  135.      to which block originally allocated by Exec it belongs. */
  136.   void *exec_block;
  137.  
  138.   /* from here on, fields only exist while the block is on the free list.
  139.      The application sees a block as a chunk of memory starting at &next */
  140.   struct free_block *next, *prev;    /* min-node compatible */
  141.   int index;
  142. };
  143.  
  144.  
  145. void
  146. init_buddy (void)
  147. {
  148.   int i, l; 
  149.  
  150.   for (l = 0; l < NUMPOOLS; l++)
  151.     {
  152.       for (i = 0; i < MAXLOG2 - MINLOG2; i++)
  153.         NewList ((struct List *) &free_list[l].buckets[i]);
  154.  
  155.       InitSemaphore (&free_list[l].sem);
  156.     }
  157. }
  158.  
  159. static inline struct free_block *
  160. unlink_block (struct free_list *fl, u_char ind, void *block)
  161. {
  162.   struct free_block *fb = (struct free_block *) block;
  163.  
  164.   if (! fb)
  165.     {
  166.       fb = (struct free_block *) RemHead ((struct List *) &fl->buckets[ind]);
  167.       if (fb)
  168.     {
  169.       fb = (struct free_block *) ((int)fb - offsetof (struct free_block, next));
  170.       fb->head = fl;
  171.   P(("    unlink_block (%s, %ld) == $%lx\n", 
  172.      fl == free_list ? "PRIVATE" : (fl == free_list + 1 ? "PUBLIC" : "BOGOUS"), ind, fb));
  173.  
  174.     }
  175.     }
  176.   else
  177.     {
  178.   P(("    unlink_block (%s, %ld, $%lx)\n", 
  179.      fl == free_list ? "PRIVATE" : (fl == free_list + 1 ? "PUBLIC" : "BOGOUS"), ind, block));
  180.  
  181.       fb->head = fl; /* free later into this pool */
  182.       Remove ((struct Node *) &fb->next);
  183.     }
  184.  
  185.   return fb;
  186. }
  187.  
  188. #if defined(DEBUG) || defined(TEST)
  189. void
  190. check_empty (int pool)
  191. {
  192.   int i;
  193.   struct free_block *fb;
  194.   
  195.   for (i = 0; i < MAXLOG2 - MINLOG2; i++)
  196.     {
  197.       while (fb = unlink_block (free_list + pool, i, 0))
  198.         {
  199.           P(("%s POOL: $%lx block @@$%lx\n",
  200.              pool ? "PUBLIC" : "PRIVATE", (1 << (i + MINLOG2)), fb));
  201.     }
  202.     }
  203. }
  204. #endif
  205.  
  206. static void inline
  207. link_block (struct free_list *fl, u_char ind, void *block)
  208. {
  209.   struct free_block *fb = (struct free_block *) block;
  210.  
  211.   P(("    link_block (%s, %ld, $%lx)\n", 
  212.       fl == free_list ? "PRIVATE" : (fl == free_list + 1 ? "PUBLIC" : "BOGOUS"), ind, block));
  213.  
  214.   fb->head = 0;    /* we're on the freelist of this pool */
  215.   fb->index = ind; /* and of this size */
  216.   AddHead ((struct List *) &fl->buckets[ind], (struct Node *) &fb->next);
  217. }
  218.  
  219. /* this is a very special log2() function that knows the upper bound
  220.    of its argument, and also automatically rounds to the next upper
  221.    power of two */
  222.  
  223. static inline int const
  224. log2 (int size)
  225. {
  226.   int pow = MAXLOG2;
  227.   int lower_bound = 1 << (MAXLOG2 - 1);
  228.  
  229.   for (;;)
  230.     {
  231.       if (size > lower_bound)
  232.         return pow;
  233.  
  234.       lower_bound >>= 1;
  235.       pow--;
  236.     }
  237. }
  238.  
  239.  
  240. static inline struct free_block *
  241. get_block (struct free_list *fl, u_char index)
  242. {
  243.   struct free_block *fb;
  244.   struct free_block *buddy;
  245.  
  246.   P(("  get_block (%s, %ld)\n", 
  247.       fl == free_list ? "PRIVATE" : (fl == free_list + 1 ? "PUBLIC" : "BOGOUS"), index));
  248.  
  249. #ifdef DEBUG
  250.   if (!fl || (fl != free_list && fl != free_list + 1))
  251.     {
  252.       ix_panic ("get_block: illegal free list!!");
  253.       return;
  254.     }
  255. #endif
  256.  
  257.   if (index == (MAXLOG2 - MINLOG2))
  258.     {
  259.       fb = (struct free_block *) AllocMem (MAXSIZE, fl->exec_attr);
  260.       if (! fb)
  261.         return 0;
  262.  
  263.       fb->exec_block = fb;    /* buddies are relative to this base address */
  264.       fb->head = fl;        /* not free */
  265.  
  266.       return fb;
  267.     }
  268.   else if (fb = unlink_block (fl, index, 0))
  269.     return fb;
  270.  
  271.   fb = get_block (fl, index + 1);
  272.  
  273.   if (fb)
  274.     {
  275.       buddy = (struct free_block *) 
  276.           ((((int)fb - (int)fb->exec_block) | (1 << (index + MINLOG2)))
  277.            + (int)fb->exec_block);
  278.  
  279. #ifdef DEBUG
  280.       if (fb == buddy)
  281.     ix_panic ("get_block: | operator should be ^ !!");
  282. #endif
  283.  
  284.       /* it is only when splitting where we have to propagate the exec
  285.          block address (verify if you like ;-)) */
  286.       buddy->exec_block = fb->exec_block;
  287.       link_block (fl, index, buddy);
  288.     }
  289.  
  290.   return fb;
  291. }
  292.  
  293.  
  294. static inline void
  295. free_block (struct free_list *fl, u_char index, struct free_block *fb)
  296. {
  297.   struct free_block *buddy;
  298.  
  299.   P(("  free_block (%s, %ld, $%lx)\n", 
  300.       fl == free_list ? "PRIVATE" : (fl == free_list + 1 ? "PUBLIC" : "BOGOUS"), index, fb));
  301.  
  302. #ifdef DEBUG
  303.   if (! fb)
  304.     {
  305.       ix_panic ("free_block: zero block!!");
  306.       return;
  307.     }
  308.  
  309.   if (!fl || (fl != free_list && fl != free_list + 1))
  310.     {
  311.       ix_panic ("free_block: illegal free list in block!!");
  312.       return;
  313.     }
  314. #endif
  315.  
  316.   buddy = (struct free_block *)
  317.       ((((int)fb - (int)fb->exec_block) ^ (1 << (index + MINLOG2)))
  318.        + (int)fb->exec_block);
  319.  
  320.   if (index == (MAXLOG2 - MINLOG2))
  321.     {
  322. #ifdef DEBUG
  323.       if (fb != fb->exec_block)
  324.         ix_panic ("free_block: fb != fb->exec_block!");
  325. #endif 
  326.       FreeMem (fb, MAXSIZE);
  327.       return;
  328.     }
  329.   else if (buddy->head || buddy->index != index)
  330.     {
  331.       /* too bad, buddy is not on freelist or of wrong size */
  332.       link_block (fl, index, fb);
  333.       return;
  334.     }
  335.  
  336.   /* reserve the buddy, then recombine both */
  337.   unlink_block (fl, index, buddy);
  338.  
  339.   /* since the buddy is free as well, recombine both blocks
  340.      and free the twice as large block */
  341.   free_block (fl, index + 1, fb < buddy ? fb : buddy);
  342. }
  343.  
  344.  
  345. void *
  346. b_alloc (int size, unsigned pool)
  347. {
  348.   u_char bucket;
  349.   struct free_block *block;
  350.   struct free_list *fl;
  351.  
  352. #ifdef DEBUG
  353.   if (pool >= NUMPOOLS)
  354.     {
  355.       ix_panic ("b_alloc: illegal pool spezified!");
  356.       return 0;
  357.     }
  358. #endif
  359.  
  360.   if (size < MINSIZE)
  361.     size = MINSIZE;
  362.  
  363.   /* the additional bytes are needed for the freelist pointer at
  364.      the beginning of each block in use and the base block originally
  365.      obtained from Exec. */
  366.     
  367.   if (size > BUDDY_LIMIT - offsetof (struct free_block, next))
  368.     return AllocMem (size, pool == PUBLIC_POOL ? MEMF_PUBLIC : 0);
  369.  
  370.   size += offsetof (struct free_block, next);
  371.  
  372.   bucket = log2 (size) - MINLOG2;
  373.   fl = free_list + pool;
  374.  
  375.   /* this once was Forbid/Permit. We're much nicer now ;-)) */
  376.   ObtainSemaphore (&fl->sem);
  377.   block = get_block (fl, bucket);
  378.   ReleaseSemaphore (&fl->sem);
  379.  
  380. #ifdef DEBUG
  381.   if (!block)
  382.     ix_panic ("b_alloc: out of memory");
  383. #endif
  384.  
  385.   P(("b_alloc ($%lx, %ld) = $%lx\n", size, pool, block));
  386.  
  387.   if (block)
  388.     return (void *) & block->next;
  389.   else
  390.     return block;
  391. }
  392.  
  393.  
  394. void
  395. b_free (struct free_block *fb, int size)
  396. {
  397.   u_char bucket;
  398.   struct free_list *fl;
  399.  
  400.   if (size < MINSIZE)
  401.     size = MINSIZE;
  402.     
  403.   if (size > BUDDY_LIMIT - offsetof (struct free_block, next))
  404.     {
  405.       FreeMem ((void *) fb, size);
  406.       return;
  407.     }
  408.  
  409.   size += offsetof (struct free_block, next);
  410.  
  411.   bucket = log2 (size) - MINLOG2;
  412.   fb = (struct free_block *) ((int)fb - offsetof (struct free_block, next));
  413.   fl = fb->head;
  414.  
  415.   P(("b_free ($%lx, $%lx)\n", fb, size));
  416.  
  417.   /* this once was Forbid/Permit. We're much nicer now ;-)) */
  418.   ObtainSemaphore (&fl->sem);
  419.   free_block (fl, bucket, fb);
  420.   ReleaseSemaphore (&fl->sem);
  421. }
  422.  
  423.  
  424. #ifdef TEST
  425. int
  426. main (int argc, char *argv[])
  427. {
  428. #ifndef PRETTY_STABLE
  429.   int i;
  430.   void *allocs[16], *bllocs[13];
  431.  
  432.   init_buddy ();
  433.   
  434.   printf ("13 allocs of pool 0\n");
  435.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  436.     {
  437.       allocs[i] = b_alloc ((i + 3) * (i + 3), 0);
  438.       memset (allocs[i], 0x34, (i + 3) * (i + 3));
  439.     }
  440.  
  441.   printf ("13 allocs of pool 1\n");
  442.   for (i = 0; i < sizeof (bllocs)/sizeof (void*); i++)
  443.     {
  444.       bllocs[i] = b_alloc ((i + 3) * (i + 3) * (i + 3), 1);
  445.       memset (bllocs[i], 0x34, (i + 3) * (i + 3) * (i + 3));
  446.     }
  447.  
  448.   printf ("13 frees of pool 1\n");
  449.   for (i = sizeof (bllocs)/sizeof (void*) - 1; i >= 0 ; i--)
  450.     b_free (bllocs[i], (i + 3) * (i + 3) * (i + 3));
  451.  
  452.   printf ("13 frees of pool 0\n");
  453.   for (i = sizeof (allocs)/sizeof (void*) - 1; i >= 0 ; i--)
  454.     b_free (allocs[i], (i + 3) * (i + 3));
  455.  
  456.  
  457.   printf ("13 allocs of pool 0\n");
  458.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  459.     {
  460.       allocs[i] = b_alloc ((i + 3) * (i + 3), 0);
  461.       memset (allocs[i], 0x34, (i + 3) * (i + 3));
  462.     }
  463.  
  464.   printf ("13 allocs of pool 1\n");
  465.   for (i = 0; i < sizeof (bllocs)/sizeof (void*); i++)
  466.     {
  467.       bllocs[i] = b_alloc ((i + 3) * (i + 3) * (i + 3), 1);
  468.       memset (bllocs[i], 0x34, (i + 3) * (i + 3) * (i + 3));
  469.     }
  470.  
  471.   printf ("13 frees of pool 1\n");
  472.   for (i = sizeof (bllocs)/sizeof (void*) - 1; i >= 0 ; i--)
  473.     b_free (bllocs[i], (i + 3) * (i + 3) * (i + 3));
  474.  
  475.   printf ("13 frees of pool 0\n");
  476.   for (i = sizeof (allocs)/sizeof (void*) - 1; i >= 0 ; i--)
  477.     b_free (allocs[i], (i + 3) * (i + 3));
  478. #else
  479.   /* run a performance comparison */
  480.   void *allocs[10000];
  481.   struct timeval tstart, tend, tdiff1, tdiff2;
  482.   int size;
  483.   int i;
  484.   
  485.   init_buddy ();
  486.  
  487.   if (argc <= 1)
  488.     size = 50;
  489.   else
  490.     size = atoi (argv[1]) ? : 50;
  491.  
  492. #if 1
  493.   gettimeofday (&tstart, 0);
  494.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  495.     {
  496.       allocs[i] = b_alloc (size, 0);
  497.       memset (allocs[i], 0x34, size);
  498.     }
  499.     
  500.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  501.     b_free (allocs[i], size);
  502.  
  503.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  504.     {
  505.       allocs[i] = b_alloc (size, 0);
  506.       memset (allocs[i], 0x34, size);
  507.     }
  508.     
  509.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  510.     b_free (allocs[i], size);
  511.  
  512. #if 0
  513.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  514.     allocs[i] = b_alloc (size, 0);
  515.     
  516.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  517.     b_free (allocs[i], size);
  518. #endif
  519.   gettimeofday (&tend, 0);
  520.   tdiff1.tv_sec = tend.tv_sec - tstart.tv_sec;
  521.   tdiff1.tv_usec = tend.tv_usec -tstart.tv_usec;
  522.   if (tdiff1.tv_usec < 0)
  523.     {
  524.       tdiff1.tv_usec += 1000000;
  525.       tdiff1.tv_sec--;
  526.     }
  527. #endif
  528.  
  529. #if 0
  530.   gettimeofday (&tstart, 0);
  531.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  532.     allocs[i] = AllocMem (size, 0);
  533.     
  534.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  535.     FreeMem (allocs[i], size);
  536.  
  537.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  538.     allocs[i] = AllocMem (size, 0);
  539.     
  540.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  541.     FreeMem (allocs[i], size);
  542.  
  543.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  544.     allocs[i] = AllocMem (size, 0);
  545.     
  546.   for (i = 0; i < sizeof (allocs)/sizeof (void*); i++)
  547.     FreeMem (allocs[i], size);
  548.   gettimeofday (&tend, 0);
  549.   tdiff2.tv_sec = tend.tv_sec - tstart.tv_sec;
  550.   tdiff2.tv_usec = tend.tv_usec -tstart.tv_usec;
  551.   if (tdiff2.tv_usec < 0)
  552.     {
  553.       tdiff2.tv_usec += 1000000;
  554.       tdiff2.tv_sec--;
  555.     }
  556. #endif
  557.  
  558.   check_empty (0);
  559.  
  560. #if 1
  561.   printf ("delta with buddy system: %d.%06d\n", tdiff1.tv_sec, tdiff1.tv_usec);
  562. #endif
  563. #if 0
  564.   printf ("delta without buddy system: %d.%06d\n", tdiff2.tv_sec, tdiff2.tv_usec);
  565. #endif
  566. #endif
  567. }
  568.  
  569. #ifndef PRETTY_STABLE
  570. test_allocmem (int size, int attr)
  571. {
  572.   int res = malloc (size);
  573.   printf ("AllocMem ($%lx, %d) = $%lx\n", size, attr, res);
  574.   return res;
  575. }
  576.  
  577. test_freemem (void *buf, int size)
  578. {
  579.   printf ("FreeMem ($%lx, $%lx)\n", buf, size);
  580. }
  581.  
  582. test_allocabs (int size, void *buf)
  583. {
  584.   return buf;
  585. }
  586. #endif
  587. #endif
  588. @
  589.  
  590.  
  591. 1.1
  592. log
  593. @Initial revision
  594. @
  595. text
  596. @d19 1
  597. a19 1
  598.  *  $Id$
  599. d21 4
  600. a24 1
  601.  *  $Log$
  602. d82 1
  603. a82 1
  604. #define BUDDY_LIMIT    (1 << (MAXLOG2 - 3))    /* but serve only upto 4K */
  605. d92 1
  606. d100 7
  607. a107 2
  608.   /* index is only used while the block is on the free list. When
  609.      allocated, this place is in use by the application */
  610. d115 6
  611. a120 4
  612.   int i; 
  613.   
  614.   for (i = 0; i < MAXLOG2 - MINLOG2; i++)
  615.     NewList ((struct List *) &free_list[0].buckets[i]);
  616. d122 2
  617. a123 2
  618.   for (i = 0; i < MAXLOG2 - MINLOG2; i++)
  619.     NewList ((struct List *) &free_list[1].buckets[i]);
  620. d226 1
  621. a226 2
  622.       /* remember we are inside Forbid! */
  623.       fb = (struct free_block *) AllocMem (2 * MAXSIZE, fl->exec_attr);
  624. d229 3
  625. a231 7
  626.       FreeMem ((void *) fb, 2 * MAXSIZE);
  627.       /* still in Forbid, so we still own the block ! Get a maximal 
  628.          aligned block out of the twice as large block */
  629.       fb = (struct free_block *) 
  630.        AllocAbs (MAXSIZE, (void *)(((int)fb + MAXSIZE - 1) & -MAXSIZE));
  631.       if (fb)
  632.     fb->head = fl;    /* not free */
  633. a241 1
  634.       /* having aligned blocks GREATLY simplifies handling of buddies.. */
  635. d243 2
  636. a244 1
  637.           ((int)fb | (1 << (index + MINLOG2)));
  638. d251 3
  639. d264 1
  640. a264 2
  641.   struct free_block *buddy = (struct free_block *) 
  642.                  ((int)fb ^ (1 << (index + MINLOG2)));
  643. d283 4
  644. d289 4
  645. d308 1
  646. a308 2
  647.   free_block (fl, index + 1, 
  648.           (struct free_block *) ((int)fb & ~(1 << (index + MINLOG2))));
  649. d330 3
  650. a332 2
  651.   /* the additional 4 bytes are needed for the freelist pointer at
  652.      the beginning of each block in use */
  653. d334 1
  654. a334 1
  655.   if (size >= BUDDY_LIMIT - offsetof (struct free_block, next))
  656. d341 3
  657. a343 1
  658.   Forbid ();
  659. d345 2
  660. a346 2
  661.   Permit ();
  662.  
  663. d370 1
  664. a370 1
  665.   if (size >= BUDDY_LIMIT - offsetof (struct free_block, next))
  666. d384 2
  667. a385 1
  668.   Forbid();
  669. d387 1
  670. a387 1
  671.   Permit();
  672. @
  673.