ia64/xen-unstable

changeset 16827:5f3c236d1711

minios: Add align support to _xmalloc().

Signed-off-by: Samuel Thibault <samuel.thibault@eu.citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Tue Jan 22 09:45:54 2008 +0000 (2008-01-22)
parents 6ba04ec03dec
children 623d668b3029
files extras/mini-os/include/xmalloc.h extras/mini-os/lib/xmalloc.c
line diff
     1.1 --- a/extras/mini-os/include/xmalloc.h	Tue Jan 22 09:44:17 2008 +0000
     1.2 +++ b/extras/mini-os/include/xmalloc.h	Tue Jan 22 09:45:54 2008 +0000
     1.3 @@ -7,7 +7,8 @@
     1.4  /* Allocate space for array of typed objects. */
     1.5  #define xmalloc_array(_type, _num) ((_type *)_xmalloc_array(sizeof(_type), __alignof__(_type), _num))
     1.6  
     1.7 -#define malloc(size) _xmalloc(size, 4)
     1.8 +#define DEFAULT_ALIGN (sizeof(unsigned long))
     1.9 +#define malloc(size) _xmalloc(size, DEFAULT_ALIGN)
    1.10  #define free(ptr) xfree(ptr)
    1.11  #define realloc(ptr, size) _realloc(ptr, size)
    1.12  
     2.1 --- a/extras/mini-os/lib/xmalloc.c	Tue Jan 22 09:44:17 2008 +0000
     2.2 +++ b/extras/mini-os/lib/xmalloc.c	Tue Jan 22 09:45:54 2008 +0000
     2.3 @@ -5,9 +5,11 @@
     2.4   *
     2.5   *        File: xmaloc.c
     2.6   *      Author: Grzegorz Milos (gm281@cam.ac.uk)
     2.7 + *              Samuel Thibault (samuel.thibault@eu.citrix.com)
     2.8   *     Changes: 
     2.9   *              
    2.10   *        Date: Aug 2005
    2.11 + *              Jan 2008
    2.12   * 
    2.13   * Environment: Xen Minimal OS
    2.14   * Description: simple memory allocator
    2.15 @@ -39,22 +41,25 @@
    2.16  #include <types.h>
    2.17  #include <lib.h>
    2.18  #include <list.h>
    2.19 +#include <xmalloc.h>
    2.20  
    2.21  static LIST_HEAD(freelist);
    2.22  /* static spinlock_t freelist_lock = SPIN_LOCK_UNLOCKED; */
    2.23  
    2.24  struct xmalloc_hdr
    2.25  {
    2.26 -    /* Total including this hdr. */
    2.27 +    /* Total including this hdr, unused padding and second hdr. */
    2.28      size_t size;
    2.29      struct list_head freelist;
    2.30 -#if defined(__ia64__)
    2.31 -		// Needed for ia64 as long as the align parameter in _xmalloc()
    2.32 -		// is not supported.
    2.33 -    uint64_t pad;
    2.34 -#endif
    2.35 +} __cacheline_aligned;
    2.36  
    2.37 -} __cacheline_aligned;
    2.38 +/* Unused padding data between the two hdrs. */
    2.39 +
    2.40 +struct xmalloc_pad
    2.41 +{
    2.42 +    /* Size including both hdrs. */
    2.43 +    size_t hdr_size;
    2.44 +};
    2.45  
    2.46  static void maybe_split(struct xmalloc_hdr *hdr, size_t size, size_t block)
    2.47  {
    2.48 @@ -62,11 +67,13 @@ static void maybe_split(struct xmalloc_h
    2.49      size_t leftover = block - size;
    2.50  
    2.51      /* If enough is left to make a block, put it on free list. */
    2.52 -    if ( leftover >= (2 * sizeof(struct xmalloc_hdr)) )
    2.53 +    if ( leftover >= (2 * (sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad))) )
    2.54      {
    2.55          extra = (struct xmalloc_hdr *)((unsigned long)hdr + size);
    2.56          extra->size = leftover;
    2.57 +        /* spin_lock_irqsave(&freelist_lock, flags); */
    2.58          list_add(&extra->freelist, &freelist);
    2.59 +        /* spin_unlock_irqrestore(&freelist_lock, flags); */
    2.60      }
    2.61      else
    2.62      {
    2.63 @@ -78,7 +85,7 @@ static void maybe_split(struct xmalloc_h
    2.64      hdr->freelist.next = hdr->freelist.prev = NULL;
    2.65  }
    2.66  
    2.67 -static void *xmalloc_new_page(size_t size)
    2.68 +static struct xmalloc_hdr *xmalloc_new_page(size_t size)
    2.69  {
    2.70      struct xmalloc_hdr *hdr;
    2.71      /* unsigned long flags; */
    2.72 @@ -87,18 +94,30 @@ static void *xmalloc_new_page(size_t siz
    2.73      if ( hdr == NULL )
    2.74          return NULL;
    2.75  
    2.76 -    /* spin_lock_irqsave(&freelist_lock, flags); */
    2.77      maybe_split(hdr, size, PAGE_SIZE);
    2.78 -    /* spin_unlock_irqrestore(&freelist_lock, flags); */
    2.79  
    2.80 -    return hdr+1;
    2.81 +    return hdr;
    2.82 +}
    2.83 +
    2.84 +/* Return size, increased to alignment with align. */
    2.85 +static inline size_t align_up(size_t size, size_t align)
    2.86 +{
    2.87 +    return (size + align - 1) & ~(align - 1);
    2.88  }
    2.89  
    2.90  /* Big object?  Just use the page allocator. */
    2.91 -static void *xmalloc_whole_pages(size_t size)
    2.92 +static void *xmalloc_whole_pages(size_t size, size_t align)
    2.93  {
    2.94      struct xmalloc_hdr *hdr;
    2.95 -    unsigned int pageorder = get_order(size);
    2.96 +    struct xmalloc_pad *pad;
    2.97 +    unsigned int pageorder;
    2.98 +    void *ret;
    2.99 +    /* Room for headers */
   2.100 +    size_t hdr_size = sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad);
   2.101 +    /* Align for actual beginning of data */
   2.102 +    hdr_size = align_up(hdr_size, align);
   2.103 +
   2.104 +    pageorder = get_order(hdr_size + size);
   2.105  
   2.106      hdr = (struct xmalloc_hdr *)alloc_pages(pageorder);
   2.107      if ( hdr == NULL )
   2.108 @@ -108,54 +127,82 @@ static void *xmalloc_whole_pages(size_t 
   2.109      /* Debugging aid. */
   2.110      hdr->freelist.next = hdr->freelist.prev = NULL;
   2.111  
   2.112 -    return hdr+1;
   2.113 -}
   2.114 -
   2.115 -/* Return size, increased to alignment with align. */
   2.116 -static inline size_t align_up(size_t size, size_t align)
   2.117 -{
   2.118 -    return (size + align - 1) & ~(align - 1);
   2.119 +    ret = (char*)hdr + hdr_size;
   2.120 +    pad = (struct xmalloc_pad *) ret - 1;
   2.121 +    pad->hdr_size = hdr_size;
   2.122 +    return ret;
   2.123  }
   2.124  
   2.125  void *_xmalloc(size_t size, size_t align)
   2.126  {
   2.127 -    struct xmalloc_hdr *i;
   2.128 +    struct xmalloc_hdr *i, *hdr = NULL;
   2.129 +    uintptr_t data_begin;
   2.130 +    size_t hdr_size;
   2.131      /* unsigned long flags; */
   2.132  
   2.133 -    /* Add room for header, pad to align next header. */
   2.134 -    size += sizeof(struct xmalloc_hdr);
   2.135 -    size = align_up(size, __alignof__(struct xmalloc_hdr));
   2.136 +    hdr_size = sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad);
   2.137 +    /* Align on headers requirements. */
   2.138 +    align = align_up(align, __alignof__(struct xmalloc_hdr));
   2.139 +    align = align_up(align, __alignof__(struct xmalloc_pad));
   2.140  
   2.141      /* For big allocs, give them whole pages. */
   2.142 -    if ( size >= PAGE_SIZE )
   2.143 -        return xmalloc_whole_pages(size);
   2.144 +    if ( size + align_up(hdr_size, align) >= PAGE_SIZE )
   2.145 +        return xmalloc_whole_pages(size, align);
   2.146  
   2.147      /* Search free list. */
   2.148      /* spin_lock_irqsave(&freelist_lock, flags); */
   2.149      list_for_each_entry( i, &freelist, freelist )
   2.150      {
   2.151 -        if ( i->size < size )
   2.152 +        data_begin = align_up((uintptr_t)i + hdr_size, align);
   2.153 +
   2.154 +        if ( data_begin + size > (uintptr_t)i + i->size )
   2.155              continue;
   2.156 +
   2.157          list_del(&i->freelist);
   2.158 -        maybe_split(i, size, i->size);
   2.159          /* spin_unlock_irqrestore(&freelist_lock, flags); */
   2.160 -        return i+1;
   2.161 +
   2.162 +        uintptr_t size_before = (data_begin - hdr_size) - (uintptr_t)i;
   2.163 +
   2.164 +        if (size_before >= 2 * hdr_size) {
   2.165 +            /* Worth splitting the beginning */
   2.166 +            struct xmalloc_hdr *new_i = (void*)(data_begin - hdr_size);
   2.167 +            new_i->size = i->size - size_before;
   2.168 +            i->size = size_before;
   2.169 +            /* spin_lock_irqsave(&freelist_lock, flags); */
   2.170 +            list_add(&i->freelist, &freelist);
   2.171 +            /* spin_unlock_irqrestore(&freelist_lock, flags); */
   2.172 +            i = new_i;
   2.173 +        }
   2.174 +        maybe_split(i, (data_begin + size) - (uintptr_t)i, i->size);
   2.175 +        hdr = i;
   2.176 +        break;
   2.177      }
   2.178 -    /* spin_unlock_irqrestore(&freelist_lock, flags); */
   2.179  
   2.180 -    /* Alloc a new page and return from that. */
   2.181 -    return xmalloc_new_page(size);
   2.182 +    if (!hdr) {
   2.183 +        /* spin_unlock_irqrestore(&freelist_lock, flags); */
   2.184 +
   2.185 +        /* Alloc a new page and return from that. */
   2.186 +        hdr = xmalloc_new_page(align_up(hdr_size, align) + size);
   2.187 +        data_begin = (uintptr_t)hdr + align_up(hdr_size, align);
   2.188 +    }
   2.189 +
   2.190 +    struct xmalloc_pad *pad = (struct xmalloc_pad *) data_begin - 1;
   2.191 +    pad->hdr_size = data_begin - (uintptr_t)hdr;
   2.192 +    BUG_ON(data_begin % align);
   2.193 +    return (void*)data_begin;
   2.194  }
   2.195  
   2.196  void xfree(const void *p)
   2.197  {
   2.198      /* unsigned long flags; */
   2.199      struct xmalloc_hdr *i, *tmp, *hdr;
   2.200 +    struct xmalloc_pad *pad;
   2.201  
   2.202      if ( p == NULL )
   2.203          return;
   2.204  
   2.205 -    hdr = (struct xmalloc_hdr *)p - 1;
   2.206 +    pad = (struct xmalloc_pad *)p - 1;
   2.207 +    hdr = (struct xmalloc_hdr *)((char *)p - pad->hdr_size);
   2.208  
   2.209      /* We know hdr will be on same page. */
   2.210      if(((long)p & PAGE_MASK) != ((long)hdr & PAGE_MASK))
   2.211 @@ -227,15 +274,19 @@ void *_realloc(void *ptr, size_t size)
   2.212  {
   2.213      void *new;
   2.214      struct xmalloc_hdr *hdr;
   2.215 +    struct xmalloc_pad *pad;
   2.216  
   2.217      if (ptr == NULL)
   2.218 -        return _xmalloc(size, 4);
   2.219 +        return _xmalloc(size, DEFAULT_ALIGN);
   2.220  
   2.221 -    hdr = (struct xmalloc_hdr *)ptr - 1;
   2.222 -    if (hdr->size >= size) 
   2.223 +    pad = (struct xmalloc_pad *)ptr - 1;
   2.224 +    hdr = (struct xmalloc_hdr *)((char*)ptr - pad->hdr_size);
   2.225 +    if (hdr->size >= size) {
   2.226 +        maybe_split(hdr, size, hdr->size);
   2.227          return ptr;
   2.228 +    }
   2.229      
   2.230 -    new = _xmalloc(size, 4);
   2.231 +    new = _xmalloc(size, DEFAULT_ALIGN);
   2.232      if (new == NULL) 
   2.233          return NULL;
   2.234