commands/elle/sbm.c

   1 /* SB - Copyright 1982 by Ken Harrenstien, SRI International
   2  *      This software is quasi-public; it may be used freely with
   3  *      like software, but may NOT be sold or made part of licensed
   4  *      products without permission of the author.  In all cases
   5  *      the source code and any modifications thereto must remain
   6  *      available to any user.
   7  *
   8  *      This is part of the SB library package.
   9  *      Any software using the SB library must likewise be made
  10  *      quasi-public, with freely available sources.
  11  */
  12
  13 #if 0
  14         This file contains the low-level memory allocation
  15 subroutines which are used by the SBLK routines.  The code here
  16 is quite machine-dependent, and the definitions in "sb.h" should be
  17 carefully checked to verify that they are correct for the target
  18 machine.
  19
  20         The ultimate low-level routine is "sbrk()" which must be
  21 provided by the system''s C library.  SBM expects that successive calls
  22 to sbrk() will return contiguous areas of memory with progressively
  23 higher addresses.  Also, the very first call to sbrk() is assumed to
  24 return a word-aligned address.
  25 #endif /*COMMENT*/
  26
  27 #include "sb.h"
  28
  29 #define FUDGE (sizeof(struct smblk))    /* Allow this much fudge in
  30                                 allocation, to prevent undue fragmentation */
  31
  32 char *(*sbm_debug)();           /* Debug switch - user-furnished routine */
  33
  34 struct smblk *sbm_nfl;          /* Pointer to node freelist */
  35 struct smblk *sbm_nxtra;        /* Reserved extra free node */
  36 struct smblk *sbm_list;         /* Pointer to smblk memory alloc list.
  37                                  * ALL smblks are strung onto this list
  38                                  * except for the freelist!
  39                                  */
  40 SBMA sbm_lowaddr;               /* Lowest word-aligned address we know about.*/
  41
  42 /* If compiling with debug switch set, use special routine in place of
  43  * sbrk so we can pretend we have a very limited area of free memory.
  44  */
  45 #ifdef DBG_SIZE
  46 #define SBM_SBRK sbm_brk
  47 char *sbm_brk();
  48 #else
  49 #define SBM_SBRK sbrk
  50 #endif /*DBG_SIZE*/
  51
  52 /* Forward routine declarations */
  53 char *sbrk();
  54 struct smblk *sbm_nmak(), *sbm_nget(), *sbm_mget(), *sbm_split();
  55 struct smblk *sbm_lmak(), *sbm_err();
  56 \f
  57 /* SBM_INIT - Initialize storage management.
  58  *      If args are zero, normal initialization is done.  Otherwise,
  59  *      args are understood to be pointers to an area of memory allocated
  60  *      on the stack (eg by an "int mem[2000]" declaration in MAIN) and
  61  *      initialization will include this area in addition to the
  62  *      unused space between "_end" and the start of the stack segment.
  63  *      This is mostly of use for PDP11s which would otherwise waste a lot
  64  *      of address space.
  65  *      Maybe should have a SBM_RESET() function?
  66  */
  67
  68 struct smblk *
  69 sbm_init(xaddr,xlen)
  70 SBMA xaddr;             /* Address of allocated stack area if any */
  71 SBMO xlen;              /* Size of this area */
  72 {       register struct smblk *sm, *sml;
  73         register char *cp;
  74
  75         /* Get initial chunk of memory from standard system rtn */
  76         if((cp = SBM_SBRK(SMNODES*sizeof(struct smblk))) == 0
  77           || (int) cp == -1)
  78                 return(sbm_err(0,"Can't sbrk"));
  79         sm = (struct smblk *)cp;                /* Better be word-aligned! */
  80         sbm_lmak(sm,(SBMO)sizeof(struct smblk),SMNODES);      /* Make list */
  81         sbm_nfl = sm;                           /* Point freelist at it */
  82         sbm_lowaddr = (SBMA)sm;                 /* Remember lowest addr seen */
  83
  84         /* Set up 1st node pointing to all memory from here on up.
  85          * We don't know exactly how much will be available at this point,
  86          * so we just pretend we have the maximum possible.
  87          */
  88         sbm_list = sml = sbm_nget();
  89         sml->smforw = sml->smback = 0;
  90         sml->smflags = SM_USE|SM_NID;           /* Initial flags */
  91         sml->smaddr = (SBMA) sml;
  92         sml->smlen = MAXSBMO;                   /* Pretend we have lots */
  93         sml->smuse = (SMNODES * sizeof(struct smblk));
  94
  95         /* Now split off everything above initial allocation as NXM. */
  96         sm = sbm_split(sml, sm->smuse);
  97         sml->smflags |= SM_MNODS;       /* Mark 1st node as having SM nodes */
  98         sm->smflags  |= SM_NXM;         /* Mark 2nd node as NXM */
  99
 100         /* Now possibly set up extra nodes, if stack mem is being allocated
 101          * (From our viewpoint it looks as if a chunk in the middle of
 102          * the initial NXM section has been declared usable)
 103          */
 104         if(xlen)
 105           {     /* Allow for "extra" static stack memory */
 106                 /* Will lose if xaddr <= 1st NXM! */
 107                 sml = sbm_split(sm, (SBMO)(xaddr - sm->smaddr));
 108                 sbm_split(sml, xlen);           /* Split off following NXM */
 109                 sml->smflags &= ~(SM_USE|SM_NXM); /* This node is free mem! */
 110           }
 111
 112         /* Now set up a small additional node which points to the NXM
 113          * that we cannot get from SBRK.  At this stage, this is just
 114          * a place-holder, to reserve the node so we don't have to
 115          * worry about running out of nodes at the same time sbrk stops
 116          * returning memory.
 117          * SM points to the NXM that we expect SBRK to dig into.
 118          */
 119         sbm_split(sm, sm->smlen - WDSIZE); /* Chop off teensy bit */
 120         sm->smflags &= ~SM_USE;         /* Now mark NXM "free"!! */
 121
 122         /* Finally, reserve an "extra" SM node for use by sbm_nget
 123          * when it is allocating more freelist node chunks.
 124          */
 125         sbm_nxtra = sbm_nget();
 126
 127         return(sbm_list);
 128 }
 129 \f
 130 /* SBM_NGET() - Get a free SM node.
 131  *      Note the hair to provide a spare SM node when
 132  *      we are allocating memory for more SM nodes.  This is necessary
 133  *      because sbm_mget and sbm_nget call each other recursively and
 134  *      sbm_mget cannot create any new memory without a SM node to point
 135  *      at the allocated chunk.
 136  */
 137 struct smblk *
 138 sbm_nget()
 139 {       register struct smblk *sm, *sml;
 140
 141         if(!(sm = sbm_nfl))             /* Get a node from freelist */
 142           {     /* Freelist is empty, try to allocate more nodes. */
 143
 144                 /* Put our "spare" smblk on freelist temporarily so that
 145                  * sbm_mget has a chance of winning.
 146                  * Infinite recursion is avoided by a test
 147                  * in sbm_mget which checks sbm_nfl and sbm_nxtra.
 148                  */
 149                 if(!(sm = sbm_nxtra))
 150                         return(sbm_err(0,"Zero sbm_nxtra!"));
 151                 sm->smforw = 0;
 152                 sbm_nfl = sm;
 153                 sbm_nxtra = 0;
 154
 155                 /* Try to allocate another chunk of SM nodes. */
 156                 sml = sbm_nmak(sizeof(struct smblk),SM_MNODS);
 157
 158                 /* Put the new free nodes (if any) on freelist.
 159                  * Done this way because freelist may have had one or two
 160                  * nodes added to it by sbm_mget, so can't just stick
 161                  * a new pointer in sbm_nfl.
 162                  */
 163                 while(sm = sml)
 164                   {     sml = sm->smforw;
 165                         sbm_nfre(sm);
 166                   }
 167
 168                 /* Now reserve an extra node again.
 169                  * It is an error if there is nothing on freelist here,
 170                  * because even if sbm_mget failed the "extra node" should
 171                  * still be on freelist.  The check for a zero sbm_nxtra
 172                  * above will catch such an error.
 173                  */
 174                 sbm_nxtra = sbm_nget();
 175
 176                 /* Now see if anything to return */
 177                 if(!(sm = sbm_nfl))             /* If freelist empty again, */
 178                         return(0);              /* give up. */
 179           }
 180         sbm_nfl = sm->smforw;   /* If win, take it off freelist */
 181         return(sm);             /* Return ptr or 0 if none */
 182 }
 183
 184 /* SBM_NFRE(sm) - Return a SM node to the SM freelist.
 185  */
 186 sbm_nfre(smp)
 187 struct smblk *smp;
 188 {       register struct smblk *sm;
 189         (sm = smp)->smflags = 0;
 190         sm->smforw = sbm_nfl;
 191         sbm_nfl = sm;
 192 }
 193
 194 /* SBM_NMAK(elsize, flag) - Make (allocate & build) a typeless node freelist.
 195  */
 196 struct smblk *
 197 sbm_nmak(elsize, flag)
 198 SBMO elsize;
 199 unsigned flag;
 200 {       register struct smblk *sm, *smp;
 201         register int cnt;
 202
 203         if((sm = sbm_mget(SMNODES*elsize,SMNODES*elsize)) == 0)
 204                 return(0);
 205
 206         sm->smflags |= flag;            /* Indicate type of nodes */
 207         cnt = sm->smlen/elsize;         /* Find # nodes that will fit */
 208         sm->smuse = cnt * elsize;       /* Actual size used */
 209         smp = (struct smblk *)(sm->smaddr);     /* Ptr to 1st loc of mem */
 210         sbm_lmak(smp, (SBMO)elsize, cnt);       /* Build freelist */
 211         return(smp);            /* Return 1st free node. Caller is */
 212                                 /* responsible for setting freelist ptr. */
 213 }
 214
 215 /* SBM_LMAK - Build freelist of typeless nodes.
 216  *      Note this does not allocate memory, it just converts an already
 217  *      allocated memory area.
 218  */
 219 struct smblk *
 220 sbm_lmak(addr, elsize, num)
 221 SBMA addr;
 222 SBMO elsize;
 223 int num;
 224 {       register struct smblk *sm, *smp;
 225         register int cnt;
 226
 227         smp = (struct smblk *) addr;
 228         if((cnt = num) <= 0)
 229                 return(0);
 230         do {    sm = smp;       /* Save ptr */
 231                 sm->smforw = (smp = (struct smblk *) ((SBMA)smp + elsize));
 232                 sm->smflags = 0;
 233           } while(--cnt);
 234         sm->smforw = 0;         /* Last node points to nothing */
 235         return(sm);             /* Return ptr to last node */
 236 }
 237
 238 /* SBM_NMOV(sm1, sm2, begp, elsize) - Move a typeless node.
 239  *      Copy sm1 to sm2, adjust ptrs, leave sm1 free.
 240  */
 241 sbm_nmov(smp1,smp2,begp,elsize)
 242 struct smblk *smp1, *smp2, **begp;
 243 int elsize;
 244 {       register struct smblk *sm;
 245
 246         bcopy((SBMA)smp1,(SBMA)(sm = smp2), elsize);     /* Copy the stuff */
 247         if(sm->smforw) sm->smforw->smback = sm; /* Fix up links */
 248         if(sm->smback) sm->smback->smforw = sm;
 249         else *begp = sm;
 250 }
 251 \f
 252 /* SBM_MGET(min,max) - Get a SMBLK with specified amount of memory.
 253  *      Returns 0 if none available.
 254  *      Memory is guaranteed to start on word boundary, but may not
 255  *              end on one.  Note that sbm_mfree is responsible for
 256  *              ensuring that free mem starts word-aligned.
 257  *      A subtle but major concern of this code is the number of freelist
 258  * nodes gobbled by a single call.  If the freelist happens to not have
 259  * enough nodes, then a recursive call to sbm_mget is made (via sbm_nget)
 260  * in order to allocate a new batch of freelist nodes!  sbm_nget will
 261  * always provide a single "spare" node during such an allocation, but
 262  * there is only one and it is essential that sbm_mget gobble only ONE
 263  * (if any) during such a call, which is indicated by sbm_nxtra==0.
 264  *      The maximum # of freelist nodes that sbm_mget can gobble is
 265  * 2, when (1) NXM memory is obtained, and a SM is needed to point at
 266  * the new free mem, plus (2) the resulting SM is too big, and has to
 267  * be split up, which requires another SM for the remainder.
 268  *      The "used-NXM" smblk is set up at init time precisely in order to
 269  * avoid the necessity of creating it here when sbrk stops winning, since
 270  * that would require yet another freelist node and make it possible for
 271  * sbm_mget to gobble 3 during one call -- too many.
 272  *      Further note: the sbm_nfl checks are necessary in order
 273  * to ensure that a SM node is available for use by sbm_split.  Otherwise
 274  * the calls to sbm_split might create a new SM freelist by gobbling the
 275  * very memory which we are hoping to return!
 276  */
 277 SBMO sbm_chksiz = SMCHUNKSIZ;   /* Current chunk size to feed sbrk */
 278
 279 struct smblk *
 280 sbm_mget(cmin,cmax)
 281 SBMO cmin,cmax;
 282 {       register struct smblk *sm, *sml;
 283         register SBMO csiz;
 284         register SBMA addr, xaddr;
 285
 286         if((sm = sbm_list) == 0         /* If never done, */
 287           && (sm = sbm_init((SBMA)0,(SBMO)0)) == 0)     /* initialize mem alloc stuff. */
 288                 return(0);              /* Can't init??? */
 289
 290         /* Round up sizes to word boundary */
 291         if(rndrem(cmin)) cmin = rndup(cmin);
 292         if(rndrem(cmax)) cmax = rndup(cmax);
 293
 294         /* Search for a free block having enough memory.
 295          * If run into a free-NXM block, always "win", since there may be
 296          * a combination of preceding free-mem and new mem which will satisfy
 297          * the request.  If it turns out this didn't work, we'll just fail
 298          * a little farther on.
 299          */
 300 retry:  csiz = cmin;                    /* Set size that will satisfy us */
 301         do {
 302                 if(  ((sm->smflags&SM_USE) == 0)
 303                   && ((sm->smlen >= csiz) || (sm->smflags&SM_NXM)) )
 304                         break;
 305           } while(sm = sm->smforw);
 306         if(sm == 0)
 307                 return(0);      /* Found none that minimum would fit */
 308
 309         if(sm->smflags&SM_NXM)
 310           {     /* Found free area, but it's marked NXM and the system
 311                  * must be persuaded (via sbrk) to let us use that portion
 312                  * of our address space.  Grab a good-sized chunk.
 313                  */
 314                 if(sbm_nfl == 0)        /* Verify a spare SM node is avail */
 315                         goto getnod;    /* Nope, must get one. */
 316
 317                 /* Decide amount of mem to ask system for, via sbrk.
 318                  * The fine point here is the check of sbm_nxtra to make sure
 319                  * that, when building more freelist nodes, we don't have
 320                  * to use more than one SM node in the process.  If we
 321                  * asked for too much mem, we'd have to use a SM node
 322                  * to hold the excess after splitting.
 323                  */
 324                 csiz = cmax;
 325                 if(sbm_nxtra            /* If normal then try for big chunk */
 326                   && csiz < sbm_chksiz) csiz = sbm_chksiz;      /* Max */
 327                 if (csiz > sm->smlen)  csiz = sm->smlen;        /* Min */
 328
 329                 /* Get the NXM mem */
 330                 if((addr = (SBMA)SBM_SBRK(csiz)) != sm->smaddr)
 331                   {     /* Unexpected value returned from SBRK! */
 332
 333                         if((int)addr != 0 && (int)addr != -1)
 334                           {     return(sbm_err(0,"SBRK %o != %o", addr,
 335                                                 sm->smaddr));
 336 #if 0
 337                         /* If value indicates couldn't get the stuff, then
 338                          * we have probably hit our limit and the rest of
 339                          * NXM should be declared "used" to prevent further
 340                          * hopeless sbrk calls.  We split off the portion
 341                          * of NXM that is known for sure to be unavailable,
 342                          * and mark it "used".  If a "used NXM" area already
 343                          * exists following this one, the two are merged.
 344                          * The chunk size is then reduced by half, so
 345                          * only log2(SMCHUNKSIZ) attempts will be made, and
 346                          * we try again.
 347                          */
 348                                 /* If returned some mem which starts outside
 349                                  * the NXM then something is screwed up. */
 350                                 if(addr < sm->smaddr
 351                                   || (addr >= sm->smaddr+sm->smlen))
 352                                         return(sbm_err(0,"SBRK %o != %o",
 353                                                 addr, sm->smaddr));
 354                                 /* Got some mem, falls within NXM.
 355                                  * Presumably someone else has called sbrk
 356                                  * since last time, so we need to fence off
 357                                  * the intervening area. */
 358                                 sm = sbm_split((sml=sm),(addr - sm->smaddr));
 359                                 sml->smflags |= SM_USE|SM_EXT;
 360                                 return(sbm_mget(cmin,cmax));
 361 #endif /*COMMENT*/
 362                           }
 363
 364                         /* Handle case of SBRK claiming no more memory.
 365                          * Gobble as much as we can, and then turn this NXM
 366                          * block into a free-mem block, and leave the
 367                          * remainder in the used-NXM block (which should
 368                          * immediately follow this free-NXM block!)
 369                          */
 370                         if(!(sml = sm->smforw)  /* Ensure have used-NXM blk */
 371                           || (sml->smflags&(SM_USE|SM_NXM))
 372                                         != (SM_USE|SM_NXM))
 373                                 return(sbm_err(0,"No uNXM node!"));
 374                         xaddr = sm->smaddr;     /* Use this for checking */
 375                         sm->smuse = 0;          /* Use this for sum */
 376                         for(csiz = sm->smlen; csiz > 0;)
 377                           {     addr = SBM_SBRK(csiz);
 378                                 if((int)addr == 0 || (int)addr == -1)
 379                                   {     csiz >>= 1;
 380                                         continue;
 381                                   }
 382                                 if(addr != xaddr)
 383                                         return(sbm_err(0,"SBRK %o != %o", addr,
 384                                                 xaddr));
 385                                 sm->smuse += csiz;
 386                                 xaddr += csiz;
 387                           }
 388
 389                         /* Have gobbled as much from SBRK as we could.
 390                          * Turn the free-NXM block into a free-mem block,
 391                          * unless we got nothing, in which case just merge
 392                          * it into the used-NXM block and continue
 393                          * searching from this point.
 394                          */
 395                         if(!(csiz = sm->smuse)) /* Get total added */
 396                           {     sm->smflags = sml->smflags;     /* Ugh. */
 397                                 sbm_mmrg(sm);
 398                                 goto retry;             /* Keep looking */
 399                           }
 400                         else
 401                           {     sml->smaddr = sm->smaddr + csiz;
 402                                 sml->smlen += sm->smlen - csiz;
 403                                 sm->smlen = csiz;
 404                                 sm->smflags &= ~SM_NXM; /* No longer NXM */
 405                           }
 406                   }
 407
 408                 /* Here when we've acquired CSIZ more memory from sbrk.
 409                  * If preceding mem area is not in use, merge new mem
 410                  * into it.
 411                  */
 412                 if((sml = sm->smback) &&
 413                   (sml->smflags&(SM_USE|SM_NXM))==0)    /* Previous free? */
 414                   {     sml->smlen += csiz;             /* Yes, simple! */
 415                         sm->smaddr += csiz;             /* Fix up */
 416                         if((sm->smlen -= csiz) == 0)    /* If no NXM left,*/
 417                                 sbm_mmrg(sml);  /* Merge NXM node w/prev */
 418                         sm = sml;               /* Prev is now winning node */
 419                   }
 420                 else
 421                   {     /* Prev node isn't a free area.  Split up the NXM
 422                          * node to account for acquired mem, unless we
 423                          * gobbled all the mem available.
 424                          */
 425                         if(sm->smlen > csiz     /* Split unless all used */
 426                           && !sbm_split(sm,csiz)) /* Call shd always win */
 427                                 return(sbm_err(0,"getsplit err: %o",sm));
 428                         sm->smflags &= ~SM_NXM; /* Node is now real mem */
 429                   }
 430
 431                 /* Now make a final check that we have enough memory.
 432                  * This can fail because SBRK may not have been able
 433                  * to gobble enough memory, either because (1) not
 434                  * as much NXM was available as we thought,
 435                  * or (2) we noticed the free-NXM area and immediately
 436                  * gambled on trying it without checking any lengths.
 437                  * In any case, we try again starting from the current SM
 438                  * because there may be more free mem higher up (eg on
 439                  * stack).
 440                  */
 441                 if(sm->smlen < cmin)
 442                         goto retry;
 443           }
 444
 445         /* Check to see if node has too much mem.  This is especially true
 446          * for memory just acquired via sbrk, which gobbles a huge chunk each
 447          * time.  If there's too much, we split up the area.
 448          */
 449         if(sm->smlen > cmax+FUDGE)      /* Got too much?  (Allow some fudge)*/
 450                 /* Yes, split up so don't gobble too much. */
 451                 if(sbm_nfl)                     /* If success guaranteed, */
 452                         sbm_split(sm,cmax);     /* split it, all's well. */
 453                 else goto getnod;
 454
 455         sm->smuse = 0;
 456         sm->smflags |= SM_USE;  /* Finally seize it by marking "in-use". */
 457         return(sm);
 458
 459         /* Come here when we will need to get another SM node but the
 460          * SM freelist is empty.  We have to forget about using the area
 461          * we just found, because sbm_nget may gobble it for the
 462          * freelist.  So, we first force a refill of the freelist, and then
 463          * invoke ourselves again on what's left.
 464          */
 465 getnod:
 466         if(sml = sbm_nget())            /* Try to build freelist */
 467           {     sbm_nfre(sml);          /* Won, give node back, */
 468                 sm = sbm_list;          /* and retry, starting over! */
 469                 goto retry;
 470           }
 471         /* Failed.  Not enough memory for both this request
 472          * and one more block of SM nodes.  Since such a SM_MNODS
 473          * block isn't very big, we are so close to the limits that it
 474          * isn't worth trying to do something fancy here to satisfy the
 475          * original request.  So we just fail.
 476          */
 477         return(0);
 478 }
 479
 480 #ifdef DBG_SIZE
 481 /* Code for debugging stuff by imposing an artificial limitation on size
 482  * of available memory.
 483  */
 484 SBMO sbm_dlim = MAXSBMO;        /* Amount of mem to allow (default is max) */
 485
 486 char *
 487 sbm_brk(size)
 488 unsigned size;
 489 {       register char *addr;
 490
 491         if(size > sbm_dlim) return(0);
 492         addr = sbrk(size);
 493         if((int)addr == 0 || (int)addr == -1)
 494                 return(0);
 495         sbm_dlim -= size;
 496         return(addr);
 497 }
 498 #endif /*DBG_SIZE*/
 499 \f
 500 /* SBM_MFREE(sm) - Free up an allocated memory area.
 501  */
 502 void
 503 sbm_mfree(sm)
 504 register struct smblk *sm;
 505 {       register struct smblk *smx;
 506         register SBMO crem;
 507
 508         sm->smflags &= ~SM_USE;                 /* Say mem is free */
 509         if((smx = sm->smback)                   /* Check preceding mem */
 510           && (smx->smflags&(SM_USE|SM_NXM))==0) /*   If it's free, */
 511                 sbm_mmrg(sm = smx);             /*   then merge 'em. */
 512         if((smx = sm->smforw)                   /* Check following mem */
 513           && (smx->smflags&(SM_USE|SM_NXM))==0) /*   Again, if free,  */
 514                 sbm_mmrg(sm);                   /*   merge them.   */
 515
 516         if(sm->smlen == 0)              /* Just in case, chk for null blk */
 517           {     if(smx = sm->smback)            /* If pred exists, */
 518                         sbm_mmrg(smx);          /* merge quietly. */
 519                 else {
 520                         sbm_list = sm->smforw;  /* 1st node on list, so */
 521                         sbm_nfre(sm);           /* simply flush it. */
 522                   }
 523                 return;
 524           }
 525
 526         /* This code is slightly over-general for some machines.
 527          * The pointer subtraction is done in order to get a valid integer
 528          * offset value regardless of the internal representation of a pointer.
 529          * We cannot reliably force alignment via casts; some C implementations
 530          * treat that as a no-op.
 531          */
 532         if(crem = rndrem(sm->smaddr - sbm_lowaddr))     /* On word bndry? */
 533           {     /* No -- must adjust.  All free mem blks MUST, by fiat,
 534                  * start on word boundary.  Here we fix things by
 535                  * making the leftover bytes belong to the previous blk,
 536                  * no matter what it is used for.  Prev blk is guaranteed to
 537                  * (1) Exist (this cannot be 1st blk since 1st is known to
 538                  * start on wd boundary) and to be (2) Non-free (else it would
 539                  * have been merged).
 540                  */
 541                 if((smx = sm->smback) == 0)     /* Get ptr to prev blk */
 542                   {     sbm_err(0,"Align err"); /* Catch screws */
 543                         return;
 544                   }
 545                 crem = WDSIZE - crem;   /* Find # bytes to flush */
 546                 if(crem >= sm->smlen)   /* Make sure node has that many */
 547                   {     sbm_mmrg(smx);  /* Flush node to avoid zero length */
 548                         return;
 549                   }
 550                 smx->smlen += crem;     /* Make stray bytes part of prev */
 551                 sm->smaddr += crem;     /* And flush from current. */
 552                 sm->smlen -= crem;
 553           }
 554 }
 555 \f
 556 /* SBM_EXP - Expand (or shrink) size of an allocated memory chunk.
 557  *      "nsize" is desired new size; may be larger or smaller than current
 558  *      size.
 559  */
 560 struct smblk *
 561 sbm_exp(sm,size)
 562 register struct smblk *sm;
 563 register SBMO size;
 564 {       register struct smblk *smf;
 565         register SBMO mexp, pred, succ;
 566
 567         if(sm->smlen >= size)           /* Do we want truncation? */
 568                 goto realo2;            /* Yup, go split block */
 569
 570         /* Block is expanding. */
 571         mexp = size - sm->smlen;                /* Get # bytes to expand by */
 572         pred = succ = 0;
 573         if((smf = sm->smforw)                   /* See if free mem follows */
 574          && (smf->smflags&(SM_USE|SM_NXM)) == 0)
 575                 if((succ = smf->smlen) >= mexp)
 576                         goto realo1;            /* Quick stuff if succ OK */
 577
 578         if((smf = sm->smback)                   /* See if free mem precedes */
 579          && (smf->smflags&(SM_USE|SM_NXM)) == 0)
 580                 pred = smf->smlen;
 581
 582         /* If not enough free space combined on both sides of this chunk,
 583          * we have to look for a completely new block.
 584          */
 585         if(pred+succ < mexp)
 586           {     if((smf = sbm_mget(size,size)) == 0)
 587                         return(0);              /* Couldn't find one */
 588                 else pred = 0;                  /* Won, indicate new block */
 589           }
 590
 591         /* OK, must copy either into new block or down into predecessor
 592          * (overlap is OK as long as bcopy moves 1st byte first)
 593          */
 594         bcopy(sm->smaddr, smf->smaddr, sm->smlen);
 595         smf->smflags = sm->smflags;     /* Copy extra attribs */
 596         smf->smuse = sm->smuse;
 597         if(!pred)                       /* If invoked sbm_mget */
 598           {     sbm_mfree(sm);          /* then must free up old area */
 599                 return(smf);            /* and can return immediately. */
 600           }
 601         sbm_mmrg(smf);                  /* Merge current into pred blk */
 602         sm = smf;                       /* Now pred is current blk. */
 603
 604         if(succ)
 605 realo1:         sbm_mmrg(sm);           /* Merge succ into current blk */
 606 realo2: if(sm->smlen > size             /* If now have too much, */
 607           && sbm_split(sm, size))       /* split up and possibly */
 608                 sbm_mfree(sm->smforw);  /* free up unused space. */
 609         return(sm);
 610
 611         /* Note that sbm_split can fail if it can't get a free node,
 612          * which is only possible if we are reducing the size of an area.
 613          * If it fails, we just return anyway without truncating the area.
 614          */
 615 }
 616 \f
 617 /* SBM_MMRG(sm) - Merge a memory area with the area following it.
 618  *      The node (and memory area) following the SM pointed to are
 619  *      merged in and the successor node freed up.  The flags
 620  *      and smuse of the current SM (which is not moved or anything)
 621  *      remain the same.
 622  */
 623 sbm_mmrg(smp)
 624 struct smblk *smp;
 625 {       register struct smblk *sm, *sm2;
 626
 627         sm = smp;
 628         sm->smlen += (sm2 = sm->smforw)->smlen; /* Add succ's len */
 629         if(sm->smforw = sm2->smforw)            /* and fix linkages */
 630                 sm->smforw->smback = sm;
 631         sbm_nfre(sm2);                          /* now can flush succ node */
 632 }
 633
 634 /* SBM_SPLIT - Split up an area (gets a new smblk to point to split-off
 635  *      portion.)
 636  * Note returned value is ptr to 2nd smblk, since this is a new one.
 637  * Ptr to 1st remains valid since original smblk stays where it is.
 638  * NOTE: Beware of splitting up free mem (SM_USE == 0) since sbm_nget may
 639  * steal it out from under unless precautions are taken!  See comments
 640  * at sbm_mget related to this.
 641  */
 642 struct smblk *
 643 sbm_split(smp,coff)
 644 struct smblk *smp;
 645 SBMO coff;
 646 {       register struct smblk *sm, *smx;
 647         register SBMO csiz;
 648
 649         if((sm = smp)->smlen <= (csiz = coff))
 650                 return(0);
 651         if((smx = sbm_nget()) == 0)
 652                 return(0);
 653         smx->smlen = sm->smlen - csiz;          /* Set 2nd size */
 654         smx->smaddr = sm->smaddr + csiz;        /* Set 2nd addr */
 655         sm->smlen = csiz;                       /* Take from 1st size */
 656         smx->smflags = sm->smflags;             /* Copy flags */
 657         if(smx->smforw = sm->smforw)            /* Splice 2nd after 1 */
 658                 smx->smforw->smback = smx;
 659         smx->smback = sm;
 660         sm->smforw = smx;                       /* Put 2nd into chain */
 661         return(smx);                            /* Return ptr to 2nd smblk */
 662 }
 663
 664 #if 0   /* Replaced by "bcopy" for system-dep efficiency */
 665 /* SBM_SCPY - Copy string of bytes.  Somewhat machine-dependent;
 666  *      Tries to be clever about using word moves instead of byte moves.
 667  */
 668 sbm_scpy(from, to, count)       /* Copy count bytes from -> to */
 669 char *from, *to;
 670 unsigned count;
 671 {       register char *s1, *s2;
 672         register unsigned cnt;
 673         int tmp;
 674
 675         if((cnt = count) == 0)
 676                 return;
 677         s1 = from;
 678         s2 = to;
 679         while(rndrem((int)s1))          /* Get 1st ptr aligned */
 680           {     *s2++ = *s1++;
 681                 if(--cnt == 0) return;
 682           }
 683         if(rndrem((int)s2) == 0)        /* Do wd move if ptr 2 now aligned */
 684           {
 685 #ifdef DUMBPCC /* Code for dumber (Portable C type) compiler */
 686                 register WORD *ap, *bp;
 687                 tmp = cnt;
 688                 ap = (WORD *) s1;
 689                 bp = (WORD *) s2;
 690                 if(cnt = rnddiv(cnt))
 691                         do { *bp++ = *ap++; }
 692                         while(--cnt);
 693                 if ((cnt = rndrem(tmp)) ==0)
 694                         return;
 695                 s1 = (char *) ap;
 696                 s2 = (char *) bp;
 697 #else
 698         /* Tight loop for efficient copying on 11s */
 699                 tmp = cnt;
 700                 if(cnt = rnddiv(cnt))
 701                         do { *((WORD *)s2)++ = *((WORD *)s1)++; }
 702                         while(--cnt);
 703                 if((cnt = rndrem(tmp)) == 0)
 704                         return;
 705 #endif /*-DUMBPCC*/
 706           }
 707         do { *s2++ = *s1++; }   /* Finish up with byte loop */
 708         while(--cnt);
 709 }
 710 #endif /*COMMENT*/
 711
 712 struct smblk *          /* If it returns at all, this is most common type */
 713 sbm_err(val,str,a0,a1,a2,a3)
 714 char *str;
 715 struct smblk *val;
 716 {       int *sptr;
 717
 718         sptr = (int *) &sptr;   /* Point to self on stack */
 719         sptr += 5;              /* Point to return addr */
 720         if((int)sbm_debug==1)
 721                 abort();
 722         if(sbm_debug)
 723                 (*sbm_debug)(0,*sptr,str,a0,a1,a2,a3);
 724         return(val);
 725 }
 726 \f
 727 /* These routines correspond to the V7 LIBC routines as described
 728  * in the V7 UPM (3).  They should provide satisfactory emulation
 729  * if the documentation is correct.  Replacement is necessary since
 730  * the SBM routines are jealous and cannot tolerate competition for
 731  * calls of SBRK; i.e. the memory being managed must be contiguous.
 732  */
 733
 734 /* Guaranteed to return word-aligned pointer to area of AT LEAST
 735  * requested size.  Area size is rounded up to word boundary.
 736  */
 737
 738 char *
 739 malloc(size)
 740 unsigned size;
 741 {       register struct smblk *sm, **sma;
 742         register SBMO siz;
 743
 744         siz = rndup(size + sizeof (struct smblk *));   /* Make room for ptr */
 745         if((sm = sbm_mget(siz,siz)) == 0)
 746                 return(0);
 747         *(sma = (struct smblk **)sm->smaddr) = sm; /* Store ptr in addr-1 */
 748         return((char *)++sma);
 749 }
 750
 751 char *
 752 alloc(size)     /* For V6 programs - note different failure value! */
 753 unsigned size;
 754 {       register char *addr;
 755         return((addr = malloc(size)) ? addr : (char *) -1);
 756 }
 757
 758 free(ptr)
 759 char *ptr;
 760 {       register struct smblk *sm, **smp;
 761
 762         smp = &((struct smblk **)ptr)[-1];      /* Point to addr-1 */
 763         sm = *smp;                              /* Pluck SM ptr therefrom */
 764         if(((sm->smflags&0377) != SM_NID) || sm->smaddr != (SBMA)smp)
 765                 return((int)sbm_err(0,"free: bad arg %o", ptr));
 766         sbm_mfree(sm);
 767         return(1);
 768 }
 769
 770 char *
 771 realloc(ptr,size)
 772 char *ptr;
 773 unsigned size;
 774 {       register struct smblk *sm, **smp;
 775
 776         smp = &((struct smblk **)ptr)[-1];      /* Point to addr-1 */
 777         sm = *smp;                              /* Pluck SM ptr therefrom */
 778         if(((sm->smflags&0377) != SM_NID) || (sm->smaddr != (SBMA)smp))
 779                 return((char *)sbm_err(0,"realloc: bad arg %o",ptr));
 780         if((sm = sbm_exp(sm, rndup(size+(sizeof(struct smblk *))))) == 0)
 781                 return(0);
 782         *(smp = (struct smblk **)sm->smaddr) = sm;      /* Save smblk ptr */
 783         return((char *)++smp);
 784 }
 785
 786 char *
 787 calloc(nelem,elsize)
 788 unsigned nelem, elsize;
 789 {       register SBMO cmin;
 790         register WORD *ip;                     /* Clear in units of words */
 791         register char *addr;
 792
 793         if((cmin = nelem*elsize) == 0           /* Find # bytes to get */
 794           || (addr = malloc(cmin)) == 0)        /* Get it */
 795                 return(0);
 796         ip = (WORD *) addr;                     /* Set up ptr to area */
 797         cmin = rnddiv(cmin+WDSIZE-1);           /* Find # words to clear */
 798         do { *ip++ = 0; } while (--cmin);       /* Zap the area */
 799         return(addr);
 800 }
 801 \f
 802 /* SBM_NGC() - Specific routine for GC'ing SMBLK nodes.
 803  *
 804  * SBM_XNGC(begp, elsize, type) - Compact nodes of specified type.
 805  *      Scans allocated mem from low to high to find chunks with nodes of
 806  *      the specified type.
 807  *      Flushes current freelist and rebuilds it as scan progresses,
 808  *      such that 1st thing on list is lowest-addr node.  When a node is
 809  *      seen that can be moved, new node is acquired from freelist if
 810  *      it exists, otherwise no move is made.  If a chunk has been scanned
 811  *      and no active nodes remain, it is flushed and freelist updated.
 812  *      NOTE: This has not yet been verified to work with nodes of any
 813  *              type other than SMBLK.
 814  */
 815
 816 sbm_ngc()
 817 {       register struct smblk *sm;
 818         if(!(sm = sbm_nxtra))
 819                 return((int)sbm_err(0,"Zero sbm_nxtra"));
 820         sm->smflags |= SM_USE;          /* Ensure this one isn't GC'd */
 821         sbm_xngc(&sbm_nfl, sizeof(struct smblk), SM_MNODS);
 822         sm->smflags = 0;                /* Flush temporary crock */
 823 }
 824 sbm_xngc(begp, elsize, flag)
 825 struct smblk **begp;
 826 unsigned elsize, flag;
 827 {       register struct smblk *sm, *chk, *smf;
 828         struct smblk *ftail, *savtail;
 829         int cnt, inuse;
 830
 831         *begp = ftail = 0;              /* Flush node freelist */
 832         for(chk = sbm_list; chk; chk = chk->smforw)
 833           if(chk->smflags&flag)
 834             {   sm = (struct smblk *) chk->smaddr;
 835                 cnt = (chk->smuse)/elsize;
 836                 savtail = ftail;
 837                 inuse = 0;
 838                 smf = *begp;
 839                                          /* Set up ptr to 1st freelist node */
 840                 while(--cnt >= 0)
 841                   {     /* Here decide if movable */
 842                         if(sm->smflags && smf   /* Live and have copy place */
 843                           && (
 844                                 (sm->smflags&SM_USE) == 0       /* Free mem? */
 845                             ||  (sm->smflags&(SM_MNODS|SM_DNODS))
 846                              )
 847                           && sm->smback)        /* has backptr (see ncpy) */
 848                           {                             /* Move the node */
 849                                 *begp = smf->smforw;    /* Get free node */
 850                                 if(smf == ftail)
 851                                         ftail = 0;
 852                                 if(smf == savtail)
 853                                         savtail = 0;
 854                                 /* Move node.  Already checked for back ptr
 855                                  * of 0 since no obvious way to tell where
 856                                  * the ptr to list is kept.  Sigh.
 857                                  */
 858                                 sbm_nmov(sm,smf,(struct smblk **)0,elsize);
 859                                 /* Get ptr to new freelist node.  Note
 860                                  * check to ensure that it is not in this
 861                                  * same chunk (if it is, no point in moving
 862                                  * any nodes!)
 863                                  */
 864                                 if((smf = *begp) >= chk)
 865                                         smf = 0;        /* Zero if same chk */
 866                                 sm->smflags = 0;        /* Make node free */
 867                           }
 868                         /* At this point, not movable */
 869                         if(sm->smflags == 0)            /* Free node? */
 870                           {     if(ftail)               /* Add to freelist */
 871                                         ftail->smforw = sm;
 872                                 ftail = sm;
 873                                 if(*begp == 0)
 874                                         *begp = sm;
 875                                 sm->smforw = 0;
 876                           }
 877                         else inuse++;
 878                         sm = (struct smblk *)((SBMA)sm + elsize);
 879                   }
 880                 if(inuse == 0                           /* All free? */
 881                   && (sm = chk->smback))                /* & not 1st? */
 882                   {     if(savtail)                     /* Edit freelist */
 883                                 (ftail = savtail)->smforw = 0;
 884                         else *begp = ftail = 0;
 885                         sbm_mfree(chk);
 886                         chk = sm;
 887                   }
 888             }
 889 }
 890
 891 /*
 892  *      Note that proc must return a zero value, or loop aborts and
 893  *      returns that selfsame value.
 894  */
 895 sbm_nfor(flag,nodsiz,proc,arg)
 896 int flag;
 897 int (*proc)();
 898 int nodsiz;
 899 struct sbfile *arg;
 900 {       register struct smblk *sm, *np;
 901         register int cnt;
 902         int res;
 903
 904         for(sm = sbm_list; sm; sm = sm->smforw)
 905           if(sm->smflags&flag)
 906             {   np = (struct smblk *) sm->smaddr;
 907                 cnt = sm->smuse/nodsiz;
 908                 do {
 909                         if(np->smflags)
 910                                 if(res = (*proc)(np,arg))
 911                                         return(res);
 912                         np = (struct smblk *)((SBMA)np + nodsiz);
 913                   } while(--cnt);
 914             }
 915         return(0);
 916 }