ia64/xen-unstable

changeset 3848:786c05f5b537

bitkeeper revision 1.1216 (42147ef15RGD4Ufi981UaX7EmpdxHQ)

Allocator cleanups.
Signed-off-by: Keir Fraser <keir@xensource.com>
author kaf24@scramble.cl.cam.ac.uk
date Thu Feb 17 11:24:33 2005 +0000 (2005-02-17)
parents 02a6b1fa80df
children 0adffee5575c
files xen/common/xmalloc.c xen/include/xen/lib.h xen/include/xen/slab.h
line diff
     1.1 --- a/xen/common/xmalloc.c	Thu Feb 17 05:37:46 2005 +0000
     1.2 +++ b/xen/common/xmalloc.c	Thu Feb 17 11:24:33 2005 +0000
     1.3 @@ -1,23 +1,31 @@
     1.4 -/* -*-  Mode:C; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
     1.5 +/* -*-  Mode:C; c-basic-offset:4; tab-width:4; indent-tabs-mode:nil -*- */
     1.6  /******************************************************************************
     1.7   * Simple allocator for Xen.  If larger than a page, simply use the
     1.8   * page-order allocator.
     1.9   *
    1.10   * Copyright (C) 2005 Rusty Russell IBM Corporation
    1.11   *
    1.12 - *  This program is free software; you can redistribute it and/or modify
    1.13 - *  it under the terms of the GNU General Public License as published by
    1.14 - *  the Free Software Foundation; either version 2 of the License, or
    1.15 - *  (at your option) any later version.
    1.16 + * This program is free software; you can redistribute it and/or modify
    1.17 + * it under the terms of the GNU General Public License as published by
    1.18 + * the Free Software Foundation; either version 2 of the License, or
    1.19 + * (at your option) any later version.
    1.20 + *
    1.21 + * This program is distributed in the hope that it will be useful,
    1.22 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
    1.23 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    1.24 + * GNU General Public License for more details.
    1.25   *
    1.26 - *  This program is distributed in the hope that it will be useful,
    1.27 - *  but WITHOUT ANY WARRANTY; without even the implied warranty of
    1.28 - *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    1.29 - *  GNU General Public License for more details.
    1.30 - *
    1.31 - *  You should have received a copy of the GNU General Public License
    1.32 - *  along with this program; if not, write to the Free Software
    1.33 - *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    1.34 + * You should have received a copy of the GNU General Public License
    1.35 + * along with this program; if not, write to the Free Software
    1.36 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    1.37 + */
    1.38 +
    1.39 +/*
    1.40 + * TODO (Keir, 17/2/05):
    1.41 + *  1. Use space in pfn_info to avoid xmalloc_hdr in allocated blocks.
    1.42 + *  2. pfn_info points into free list to make xfree() O(1) complexity.
    1.43 + *  3. Perhaps make this a sub-page buddy allocator? xmalloc() == O(1).
    1.44 + *     (Disadvantage is potentially greater internal fragmentation).
    1.45   */
    1.46  
    1.47  #include <xen/mm.h>
    1.48 @@ -25,157 +33,170 @@
    1.49  #include <xen/ac_timer.h>
    1.50  #include <xen/cache.h>
    1.51  
    1.52 -#define BUG_ON(x) do { if (x) BUG(); } while(0)
    1.53 -
    1.54  static LIST_HEAD(freelist);
    1.55  static spinlock_t freelist_lock = SPIN_LOCK_UNLOCKED;
    1.56  
    1.57  struct xmalloc_hdr
    1.58  {
    1.59 -	/* Total including this hdr. */
    1.60 -	size_t size;
    1.61 -	struct list_head freelist;
    1.62 +    /* Total including this hdr. */
    1.63 +    size_t size;
    1.64 +    struct list_head freelist;
    1.65  } __attribute__((__aligned__(SMP_CACHE_BYTES)));
    1.66  
    1.67  static void maybe_split(struct xmalloc_hdr *hdr, size_t size, size_t block)
    1.68  {
    1.69 -	size_t leftover = block - size;
    1.70 -
    1.71 -	/* If enough left to make a block, put it on free list. */
    1.72 -	if (leftover >= sizeof(struct xmalloc_hdr)) {
    1.73 -		struct xmalloc_hdr *extra;
    1.74 +    struct xmalloc_hdr *extra;
    1.75 +    size_t leftover = block - size;
    1.76  
    1.77 -		extra = (void *)hdr + size;
    1.78 -		extra->size = leftover;
    1.79 -		list_add(&extra->freelist, &freelist);
    1.80 -	} else {
    1.81 -		size = block;
    1.82 -	}
    1.83 +    /* If enough is left to make a block, put it on free list. */
    1.84 +    if ( leftover >= (2 * sizeof(struct xmalloc_hdr)) )
    1.85 +    {
    1.86 +        extra = (struct xmalloc_hdr *)((unsigned long)hdr + size);
    1.87 +        extra->size = leftover;
    1.88 +        list_add(&extra->freelist, &freelist);
    1.89 +    }
    1.90 +    else
    1.91 +    {
    1.92 +        size = block;
    1.93 +    }
    1.94  
    1.95 -	hdr->size = size;
    1.96 -	/* Debugging aid. */
    1.97 -	hdr->freelist.next = hdr->freelist.prev = NULL;
    1.98 +    hdr->size = size;
    1.99 +    /* Debugging aid. */
   1.100 +    hdr->freelist.next = hdr->freelist.prev = NULL;
   1.101  }
   1.102  
   1.103  static void *xmalloc_new_page(size_t size)
   1.104  {
   1.105 -	struct xmalloc_hdr *hdr;
   1.106 -	unsigned long flags;
   1.107 +    struct xmalloc_hdr *hdr;
   1.108 +    unsigned long flags;
   1.109  
   1.110 -	hdr = (void *)alloc_xenheap_pages(0);
   1.111 -	if (hdr == NULL)
   1.112 -		return NULL;
   1.113 +    hdr = (struct xmalloc_hdr *)alloc_xenheap_pages(0);
   1.114 +    if ( hdr == NULL )
   1.115 +        return NULL;
   1.116  
   1.117 -	spin_lock_irqsave(&freelist_lock, flags);
   1.118 -	maybe_split(hdr, size, PAGE_SIZE);
   1.119 -	spin_unlock_irqrestore(&freelist_lock, flags);
   1.120 -	return hdr+1;
   1.121 +    spin_lock_irqsave(&freelist_lock, flags);
   1.122 +    maybe_split(hdr, size, PAGE_SIZE);
   1.123 +    spin_unlock_irqrestore(&freelist_lock, flags);
   1.124 +
   1.125 +    return hdr+1;
   1.126  }
   1.127  
   1.128 -/* Big object?  Just use page allocator. */
   1.129 +/* Big object?  Just use the page allocator. */
   1.130  static void *xmalloc_whole_pages(size_t size)
   1.131  {
   1.132 -	struct xmalloc_hdr *hdr;
   1.133 -	unsigned int pageorder = get_order(size);
   1.134 +    struct xmalloc_hdr *hdr;
   1.135 +    unsigned int pageorder = get_order(size);
   1.136  
   1.137 -	hdr = (void *)alloc_xenheap_pages(pageorder);
   1.138 -	if (hdr == NULL)
   1.139 -		return NULL;
   1.140 +    hdr = (struct xmalloc_hdr *)alloc_xenheap_pages(pageorder);
   1.141 +    if ( hdr == NULL )
   1.142 +        return NULL;
   1.143  
   1.144 -	hdr->size = (1 << (pageorder + PAGE_SHIFT));
   1.145 -	/* Debugging aid. */
   1.146 -	hdr->freelist.next = hdr->freelist.prev = NULL;
   1.147 -	return hdr+1;
   1.148 +    hdr->size = (1 << (pageorder + PAGE_SHIFT));
   1.149 +    /* Debugging aid. */
   1.150 +    hdr->freelist.next = hdr->freelist.prev = NULL;
   1.151 +
   1.152 +    return hdr+1;
   1.153  }
   1.154  
   1.155  /* Return size, increased to alignment with align. */
   1.156  static inline size_t align_up(size_t size, size_t align)
   1.157  {
   1.158 -	return (size + align-1) & ~(align - 1);
   1.159 +    return (size + align - 1) & ~(align - 1);
   1.160  }
   1.161  
   1.162  void *_xmalloc(size_t size, size_t align)
   1.163  {
   1.164 -	struct xmalloc_hdr *i;
   1.165 -	unsigned long flags;
   1.166 +    struct xmalloc_hdr *i;
   1.167 +    unsigned long flags;
   1.168  
   1.169 -	/* We currently always return cacheline aligned. */
   1.170 -	BUG_ON(align > SMP_CACHE_BYTES);
   1.171 +    /* We currently always return cacheline aligned. */
   1.172 +    BUG_ON(align > SMP_CACHE_BYTES);
   1.173  
   1.174 -	/* Add room for header, pad to align next header. */
   1.175 -	size += sizeof(struct xmalloc_hdr);
   1.176 -	size = align_up(size, __alignof__(struct xmalloc_hdr));
   1.177 +    /* Add room for header, pad to align next header. */
   1.178 +    size += sizeof(struct xmalloc_hdr);
   1.179 +    size = align_up(size, __alignof__(struct xmalloc_hdr));
   1.180  
   1.181 -	/* For big allocs, give them whole pages. */
   1.182 -	if (size >= PAGE_SIZE)
   1.183 -		return xmalloc_whole_pages(size);
   1.184 +    /* For big allocs, give them whole pages. */
   1.185 +    if ( size >= PAGE_SIZE )
   1.186 +        return xmalloc_whole_pages(size);
   1.187  
   1.188 -	/* Search free list */
   1.189 -	spin_lock_irqsave(&freelist_lock, flags);
   1.190 -	list_for_each_entry(i, &freelist, freelist) {
   1.191 -		if (i->size >= size) {
   1.192 -			list_del(&i->freelist);
   1.193 -			maybe_split(i, size, i->size);
   1.194 -			spin_unlock_irqrestore(&freelist_lock, flags);
   1.195 -			return i+1;
   1.196 -		}
   1.197 -	}
   1.198 -	spin_unlock_irqrestore(&freelist_lock, flags);
   1.199 +    /* Search free list. */
   1.200 +    spin_lock_irqsave(&freelist_lock, flags);
   1.201 +    list_for_each_entry( i, &freelist, freelist )
   1.202 +    {
   1.203 +        if ( i->size < size )
   1.204 +            continue;
   1.205 +        list_del(&i->freelist);
   1.206 +        maybe_split(i, size, i->size);
   1.207 +        spin_unlock_irqrestore(&freelist_lock, flags);
   1.208 +        return i+1;
   1.209 +    }
   1.210 +    spin_unlock_irqrestore(&freelist_lock, flags);
   1.211  
   1.212 -	/* Alloc a new page and return from that. */
   1.213 -	return xmalloc_new_page(size);
   1.214 +    /* Alloc a new page and return from that. */
   1.215 +    return xmalloc_new_page(size);
   1.216  }
   1.217  
   1.218  void xfree(const void *p)
   1.219  {
   1.220 -	unsigned long flags;
   1.221 -	struct xmalloc_hdr *i, *tmp, *hdr;
   1.222 +    unsigned long flags;
   1.223 +    struct xmalloc_hdr *i, *tmp, *hdr;
   1.224 +
   1.225 +    if ( p == NULL )
   1.226 +        return;
   1.227  
   1.228 -	if (p == NULL)
   1.229 -		return;
   1.230 +    hdr = (struct xmalloc_hdr *)p - 1;
   1.231  
   1.232 -	hdr = (struct xmalloc_hdr *)p - 1;
   1.233 +    /* We know hdr will be on same page. */
   1.234 +    BUG_ON(((long)p & PAGE_MASK) != ((long)hdr & PAGE_MASK));
   1.235 +
   1.236 +    /* Not previously freed. */
   1.237 +    BUG_ON(hdr->freelist.next || hdr->freelist.prev);
   1.238  
   1.239 -	/* We know hdr will be on same page. */
   1.240 -	BUG_ON(((long)p & PAGE_MASK) != ((long)hdr & PAGE_MASK));
   1.241 -
   1.242 -	/* Not previously freed. */
   1.243 -	BUG_ON(hdr->freelist.next || hdr->freelist.prev);
   1.244 +    /* Big allocs free directly. */
   1.245 +    if ( hdr->size >= PAGE_SIZE )
   1.246 +    {
   1.247 +        free_xenheap_pages((unsigned long)hdr, get_order(hdr->size));
   1.248 +        return;
   1.249 +    }
   1.250  
   1.251 -	/* Big allocs free directly. */
   1.252 -	if (hdr->size >= PAGE_SIZE) {
   1.253 -		free_xenheap_pages((unsigned long)hdr, get_order(hdr->size));
   1.254 -		return;
   1.255 -	}
   1.256 +    /* Merge with other free block, or put in list. */
   1.257 +    spin_lock_irqsave(&freelist_lock, flags);
   1.258 +    list_for_each_entry_safe( i, tmp, &freelist, freelist )
   1.259 +    {
   1.260 +        unsigned long _i   = (unsigned long)i;
   1.261 +        unsigned long _hdr = (unsigned long)hdr;
   1.262  
   1.263 -	/* Merge with other free block, or put in list. */
   1.264 -	spin_lock_irqsave(&freelist_lock, flags);
   1.265 -	list_for_each_entry_safe(i, tmp, &freelist, freelist) {
   1.266 -		unsigned long _i   = (unsigned long)i;
   1.267 -		unsigned long _hdr = (unsigned long)hdr;
   1.268 -		/* Do not merge across page boundaries. */
   1.269 -		if (((_i ^ _hdr) & PAGE_MASK) != 0)
   1.270 -			continue;
   1.271 -		/* We follow this block?  Swallow it. */
   1.272 -		if ((_i + i->size) == _hdr) {
   1.273 -			list_del(&i->freelist);
   1.274 -			i->size += hdr->size;
   1.275 -			hdr = i;
   1.276 -		}
   1.277 -		/* We precede this block? Swallow it. */
   1.278 -		if ((_hdr + hdr->size) == _i) {
   1.279 -			list_del(&i->freelist);
   1.280 -			hdr->size += i->size;
   1.281 -		}
   1.282 -	}
   1.283 +        /* Do not merge across page boundaries. */
   1.284 +        if ( ((_i ^ _hdr) & PAGE_MASK) != 0 )
   1.285 +            continue;
   1.286 +
   1.287 +        /* We follow this block?  Swallow it. */
   1.288 +        if ( (_i + i->size) == _hdr )
   1.289 +        {
   1.290 +            list_del(&i->freelist);
   1.291 +            i->size += hdr->size;
   1.292 +            hdr = i;
   1.293 +        }
   1.294  
   1.295 -	/* Did we free entire page? */
   1.296 -	if (hdr->size == PAGE_SIZE) {
   1.297 -		BUG_ON((((unsigned long)hdr) & (PAGE_SIZE-1)) != 0);
   1.298 -		free_xenheap_pages((unsigned long)hdr, 0);
   1.299 -	} else {
   1.300 -		list_add(&hdr->freelist, &freelist);
   1.301 -	}
   1.302 +        /* We precede this block? Swallow it. */
   1.303 +        if ( (_hdr + hdr->size) == _i )
   1.304 +        {
   1.305 +            list_del(&i->freelist);
   1.306 +            hdr->size += i->size;
   1.307 +        }
   1.308 +    }
   1.309  
   1.310 -	spin_unlock_irqrestore(&freelist_lock, flags);
   1.311 +    /* Did we merge an entire page? */
   1.312 +    if ( hdr->size == PAGE_SIZE )
   1.313 +    {
   1.314 +        BUG_ON((((unsigned long)hdr) & (PAGE_SIZE-1)) != 0);
   1.315 +        free_xenheap_pages((unsigned long)hdr, 0);
   1.316 +    }
   1.317 +    else
   1.318 +    {
   1.319 +        list_add(&hdr->freelist, &freelist);
   1.320 +    }
   1.321 +
   1.322 +    spin_unlock_irqrestore(&freelist_lock, flags);
   1.323  }
     2.1 --- a/xen/include/xen/lib.h	Thu Feb 17 05:37:46 2005 +0000
     2.2 +++ b/xen/include/xen/lib.h	Thu Feb 17 11:24:33 2005 +0000
     2.3 @@ -12,6 +12,8 @@
     2.4      FORCE_CRASH();                                      \
     2.5  } while ( 0 )
     2.6  
     2.7 +#define BUG_ON(_p) do { if (_p) BUG(); } while ( 0 )
     2.8 +
     2.9  #ifndef NDEBUG
    2.10  #define ASSERT(_p) if ( !(_p) ) { printk("Assertion '%s' failed, line %d, file %s\n", #_p , __LINE__, __FILE__); BUG(); }
    2.11  #else
     3.1 --- a/xen/include/xen/slab.h	Thu Feb 17 05:37:46 2005 +0000
     3.2 +++ b/xen/include/xen/slab.h	Thu Feb 17 11:24:33 2005 +0000
     3.3 @@ -1,7 +1,3 @@
     3.4 -/*
     3.5 - * Written by Mark Hemment, 1996.
     3.6 - * (markhe@nextd.demon.co.uk)
     3.7 - */
     3.8  
     3.9  #ifndef __SLAB_H__
    3.10  #define __SLAB_H__