ia64/xen-unstable

changeset 18707:734a5493f03a

Remove unused old xmalloc.c file.
Signed-off-by: Keir Fraser <keir.fraser@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Wed Oct 22 16:39:37 2008 +0100 (2008-10-22)
parents 94227875c13d
children 71faca83998d
files xen/common/xmalloc.c
line diff
     1.1 --- a/xen/common/xmalloc.c	Wed Oct 22 15:11:54 2008 +0100
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,286 +0,0 @@
     1.4 -/******************************************************************************
     1.5 - * Simple allocator for Xen.  If larger than a page, simply use the
     1.6 - * page-order allocator.
     1.7 - *
     1.8 - * Copyright (C) 2005 Rusty Russell IBM Corporation
     1.9 - *
    1.10 - * This program is free software; you can redistribute it and/or modify
    1.11 - * it under the terms of the GNU General Public License as published by
    1.12 - * the Free Software Foundation; either version 2 of the License, or
    1.13 - * (at your option) any later version.
    1.14 - *
    1.15 - * This program is distributed in the hope that it will be useful,
    1.16 - * but WITHOUT ANY WARRANTY; without even the implied warranty of
    1.17 - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    1.18 - * GNU General Public License for more details.
    1.19 - *
    1.20 - * You should have received a copy of the GNU General Public License
    1.21 - * along with this program; if not, write to the Free Software
    1.22 - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    1.23 - */
    1.24 -
    1.25 -/*
    1.26 - * TODO (Keir, 17/2/05):
    1.27 - *  1. Use space in page_info to avoid xmalloc_hdr in allocated blocks.
    1.28 - *  2. page_info points into free list to make xfree() O(1) complexity.
    1.29 - *  3. Perhaps make this a sub-page buddy allocator? xmalloc() == O(1).
    1.30 - *     (Disadvantage is potentially greater internal fragmentation).
    1.31 - */
    1.32 -
    1.33 -#include <xen/config.h>
    1.34 -#include <xen/mm.h>
    1.35 -#include <xen/spinlock.h>
    1.36 -#include <xen/timer.h>
    1.37 -#include <xen/cache.h>
    1.38 -#include <xen/prefetch.h>
    1.39 -#include <xen/irq.h>
    1.40 -#include <xen/smp.h>
    1.41 -
    1.42 -/*
    1.43 - * XMALLOC_DEBUG:
    1.44 - *  1. Free data blocks are filled with poison bytes.
    1.45 - *  2. In-use data blocks have guard bytes at the start and end.
    1.46 - */
    1.47 -#ifndef NDEBUG
    1.48 -#define XMALLOC_DEBUG 1
    1.49 -#endif
    1.50 -
    1.51 -static LIST_HEAD(freelist);
    1.52 -static DEFINE_SPINLOCK(freelist_lock);
    1.53 -
    1.54 -struct xmalloc_hdr
    1.55 -{
    1.56 -    /* Size is total including this header. */
    1.57 -    size_t size;
    1.58 -    struct list_head freelist;
    1.59 -} __cacheline_aligned;
    1.60 -
    1.61 -static void add_to_freelist(struct xmalloc_hdr *hdr)
    1.62 -{
    1.63 -#if XMALLOC_DEBUG
    1.64 -    memset(hdr + 1, 0xa5, hdr->size - sizeof(*hdr));
    1.65 -#endif
    1.66 -    list_add(&hdr->freelist, &freelist);
    1.67 -}
    1.68 -
    1.69 -static void del_from_freelist(struct xmalloc_hdr *hdr)
    1.70 -{
    1.71 -#if XMALLOC_DEBUG
    1.72 -    size_t i;
    1.73 -    unsigned char *data = (unsigned char *)(hdr + 1);
    1.74 -    for ( i = 0; i < (hdr->size - sizeof(*hdr)); i++ )
    1.75 -        BUG_ON(data[i] != 0xa5);
    1.76 -    BUG_ON((hdr->size <= 0) || (hdr->size >= PAGE_SIZE));
    1.77 -#endif
    1.78 -    list_del(&hdr->freelist);
    1.79 -}
    1.80 -
    1.81 -static void *data_from_header(struct xmalloc_hdr *hdr)
    1.82 -{
    1.83 -#if XMALLOC_DEBUG
    1.84 -    /* Data block contain SMP_CACHE_BYTES of guard canary. */
    1.85 -    unsigned char *data = (unsigned char *)(hdr + 1);
    1.86 -    memset(data, 0x5a, SMP_CACHE_BYTES);
    1.87 -    memset(data + hdr->size - sizeof(*hdr) - SMP_CACHE_BYTES,
    1.88 -           0x5a, SMP_CACHE_BYTES);
    1.89 -    return data + SMP_CACHE_BYTES;
    1.90 -#else
    1.91 -    return hdr + 1;
    1.92 -#endif
    1.93 -}
    1.94 -
    1.95 -static struct xmalloc_hdr *header_from_data(void *p)
    1.96 -{
    1.97 -#if XMALLOC_DEBUG
    1.98 -    unsigned char *data = (unsigned char *)p - SMP_CACHE_BYTES;
    1.99 -    struct xmalloc_hdr *hdr = (struct xmalloc_hdr *)data - 1;
   1.100 -    size_t i;
   1.101 -
   1.102 -    /* Check header guard canary. */
   1.103 -    for ( i = 0; i < SMP_CACHE_BYTES; i++ )
   1.104 -        BUG_ON(data[i] != 0x5a);
   1.105 -
   1.106 -    /* Check footer guard canary. */
   1.107 -    data += hdr->size - sizeof(*hdr) - SMP_CACHE_BYTES;
   1.108 -    for ( i = 0; i < SMP_CACHE_BYTES; i++ )
   1.109 -        BUG_ON(data[i] != 0x5a);
   1.110 -
   1.111 -    return hdr;
   1.112 -#else
   1.113 -    return (struct xmalloc_hdr *)p - 1;
   1.114 -#endif
   1.115 -}
   1.116 -
   1.117 -static void maybe_split(struct xmalloc_hdr *hdr, size_t size, size_t block)
   1.118 -{
   1.119 -    struct xmalloc_hdr *extra;
   1.120 -    size_t leftover = block - size;
   1.121 -
   1.122 -    /* If enough is left to make a block, put it on free list. */
   1.123 -    if ( leftover >= (2 * sizeof(struct xmalloc_hdr)) )
   1.124 -    {
   1.125 -        extra = (struct xmalloc_hdr *)((unsigned long)hdr + size);
   1.126 -        extra->size = leftover;
   1.127 -        add_to_freelist(extra);
   1.128 -    }
   1.129 -    else
   1.130 -    {
   1.131 -        size = block;
   1.132 -    }
   1.133 -
   1.134 -    hdr->size = size;
   1.135 -    /* Debugging aid. */
   1.136 -    hdr->freelist.next = hdr->freelist.prev = NULL;
   1.137 -}
   1.138 -
   1.139 -static void *xmalloc_new_page(size_t size)
   1.140 -{
   1.141 -    struct xmalloc_hdr *hdr;
   1.142 -
   1.143 -    hdr = alloc_xenheap_page();
   1.144 -    if ( hdr == NULL )
   1.145 -        return NULL;
   1.146 -
   1.147 -    spin_lock(&freelist_lock);
   1.148 -    maybe_split(hdr, size, PAGE_SIZE);
   1.149 -    spin_unlock(&freelist_lock);
   1.150 -
   1.151 -    return data_from_header(hdr);
   1.152 -}
   1.153 -
   1.154 -/* Big object?  Just use the page allocator. */
   1.155 -static void *xmalloc_whole_pages(size_t size)
   1.156 -{
   1.157 -    struct xmalloc_hdr *hdr;
   1.158 -    unsigned int pageorder = get_order_from_bytes(size);
   1.159 -
   1.160 -    hdr = alloc_xenheap_pages(pageorder);
   1.161 -    if ( hdr == NULL )
   1.162 -        return NULL;
   1.163 -
   1.164 -    hdr->size = (1 << (pageorder + PAGE_SHIFT));
   1.165 -    /* Debugging aid. */
   1.166 -    hdr->freelist.next = hdr->freelist.prev = NULL;
   1.167 -
   1.168 -    return data_from_header(hdr);
   1.169 -}
   1.170 -
   1.171 -/* Return size, increased to alignment with align. */
   1.172 -static inline size_t align_up(size_t size, size_t align)
   1.173 -{
   1.174 -    return (size + align - 1) & ~(align - 1);
   1.175 -}
   1.176 -
   1.177 -void *_xmalloc(size_t size, size_t align)
   1.178 -{
   1.179 -    struct xmalloc_hdr *i;
   1.180 -
   1.181 -    ASSERT(!in_irq());
   1.182 -
   1.183 -    /* We currently always return cacheline aligned. */
   1.184 -    BUG_ON(align > SMP_CACHE_BYTES);
   1.185 -
   1.186 -#if XMALLOC_DEBUG
   1.187 -    /* Add room for canaries at start and end of data block. */
   1.188 -    size += 2 * SMP_CACHE_BYTES;
   1.189 -#endif
   1.190 -
   1.191 -    /* Add room for header, pad to align next header. */
   1.192 -    size += sizeof(struct xmalloc_hdr);
   1.193 -    size = align_up(size, __alignof__(struct xmalloc_hdr));
   1.194 -
   1.195 -    /* For big allocs, give them whole pages. */
   1.196 -    if ( size >= PAGE_SIZE )
   1.197 -        return xmalloc_whole_pages(size);
   1.198 -
   1.199 -    /* Search free list. */
   1.200 -    spin_lock(&freelist_lock);
   1.201 -    list_for_each_entry( i, &freelist, freelist )
   1.202 -    {
   1.203 -        if ( i->size < size )
   1.204 -            continue;
   1.205 -        del_from_freelist(i);
   1.206 -        maybe_split(i, size, i->size);
   1.207 -        spin_unlock(&freelist_lock);
   1.208 -        return data_from_header(i);
   1.209 -    }
   1.210 -    spin_unlock(&freelist_lock);
   1.211 -
   1.212 -    /* Alloc a new page and return from that. */
   1.213 -    return xmalloc_new_page(size);
   1.214 -}
   1.215 -
   1.216 -void xfree(void *p)
   1.217 -{
   1.218 -    struct xmalloc_hdr *i, *tmp, *hdr;
   1.219 -
   1.220 -    ASSERT(!in_irq());
   1.221 -
   1.222 -    if ( p == NULL )
   1.223 -        return;
   1.224 -
   1.225 -    hdr = header_from_data(p);
   1.226 -
   1.227 -    /* We know hdr will be on same page. */
   1.228 -    BUG_ON(((long)p & PAGE_MASK) != ((long)hdr & PAGE_MASK));
   1.229 -
   1.230 -    /* Not previously freed. */
   1.231 -    BUG_ON(hdr->freelist.next || hdr->freelist.prev);
   1.232 -
   1.233 -    /* Big allocs free directly. */
   1.234 -    if ( hdr->size >= PAGE_SIZE )
   1.235 -    {
   1.236 -        free_xenheap_pages(hdr, get_order_from_bytes(hdr->size));
   1.237 -        return;
   1.238 -    }
   1.239 -
   1.240 -    /* Merge with other free block, or put in list. */
   1.241 -    spin_lock(&freelist_lock);
   1.242 -    list_for_each_entry_safe( i, tmp, &freelist, freelist )
   1.243 -    {
   1.244 -        unsigned long _i   = (unsigned long)i;
   1.245 -        unsigned long _hdr = (unsigned long)hdr;
   1.246 -
   1.247 -        /* Do not merge across page boundaries. */
   1.248 -        if ( ((_i ^ _hdr) & PAGE_MASK) != 0 )
   1.249 -            continue;
   1.250 -
   1.251 -        /* We follow this block?  Swallow it. */
   1.252 -        if ( (_i + i->size) == _hdr )
   1.253 -        {
   1.254 -            del_from_freelist(i);
   1.255 -            i->size += hdr->size;
   1.256 -            hdr = i;
   1.257 -        }
   1.258 -
   1.259 -        /* We precede this block? Swallow it. */
   1.260 -        if ( (_hdr + hdr->size) == _i )
   1.261 -        {
   1.262 -            del_from_freelist(i);
   1.263 -            hdr->size += i->size;
   1.264 -        }
   1.265 -    }
   1.266 -
   1.267 -    /* Did we merge an entire page? */
   1.268 -    if ( hdr->size == PAGE_SIZE )
   1.269 -    {
   1.270 -        BUG_ON((((unsigned long)hdr) & (PAGE_SIZE-1)) != 0);
   1.271 -        free_xenheap_pages(hdr, 0);
   1.272 -    }
   1.273 -    else
   1.274 -    {
   1.275 -        add_to_freelist(hdr);
   1.276 -    }
   1.277 -
   1.278 -    spin_unlock(&freelist_lock);
   1.279 -}
   1.280 -
   1.281 -/*
   1.282 - * Local variables:
   1.283 - * mode: C
   1.284 - * c-set-style: "BSD"
   1.285 - * c-basic-offset: 4
   1.286 - * tab-width: 4
   1.287 - * indent-tabs-mode: nil
   1.288 - * End:
   1.289 - */