user/umalloc.c

1#include "kernel/types.h"2#include "kernel/stat.h"3#include "user/user.h"4#include "kernel/param.h"56// Memory allocator by Kernighan and Ritchie,7// The C programming Language, 2nd ed.  Section 8.7.89typedef long Align;1011union header {12  struct {13    union header *ptr;14    uint size;15  } s;16  Align x;17};1819typedef union header Header;2021static Header base;22static Header *freep;2324void25free(void *ap)26{27  Header *bp, *p;2829  bp = (Header*)ap - 1;30  for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)31    if(p >= p->s.ptr && (bp > p || bp < p->s.ptr))32      break;33  if(bp + bp->s.size == p->s.ptr){34    bp->s.size += p->s.ptr->s.size;35    bp->s.ptr = p->s.ptr->s.ptr;36  } else37    bp->s.ptr = p->s.ptr;38  if(p + p->s.size == bp){39    p->s.size += bp->s.size;40    p->s.ptr = bp->s.ptr;41  } else42    p->s.ptr = bp;43  freep = p;44}4546static Header*47morecore(uint nu)48{49  char *p;50  Header *hp;5152  if(nu < 4096)53    nu = 4096;54  p = sbrk(nu * sizeof(Header));55  if(p == SBRK_ERROR)56    return 0;57  hp = (Header*)p;58  hp->s.size = nu;59  free((void*)(hp + 1));60  return freep;61}6263void*64malloc(uint nbytes)65{66  Header *p, *prevp;67  uint nunits;6869  nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;70  if((prevp = freep) == 0){71    base.s.ptr = freep = prevp = &base;72    base.s.size = 0;73  }74  for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){75    if(p->s.size >= nunits){76      if(p->s.size == nunits)77        prevp->s.ptr = p->s.ptr;78      else {79        p->s.size -= nunits;80        p += p->s.size;81        p->s.size = nunits;82      }83      freep = prevp;84      return (void*)(p + 1);85    }86    if(p == freep)87      if((p = morecore(nunits)) == 0)88        return 0;89  }90}91