ia64/xen-unstable

changeset 1933:9975cd31ac46

bitkeeper revision 1.1108.23.4 (41066cd5HJomAoRwJhBHUSUuquTXoQ)

Buddy allocator no longer threads lists thru the free pages themselves.
author kaf24@scramble.cl.cam.ac.uk
date Tue Jul 27 14:55:17 2004 +0000 (2004-07-27)
parents 8c6aa4b97dfc
children 9711b428cf6a 613602e2d771
files xen/common/page_alloc.c
line diff
     1.1 --- a/xen/common/page_alloc.c	Tue Jul 27 13:40:31 2004 +0000
     1.2 +++ b/xen/common/page_alloc.c	Tue Jul 27 14:55:17 2004 +0000
     1.3 @@ -3,7 +3,7 @@
     1.4   * 
     1.5   * Simple buddy heap allocator for Xen.
     1.6   * 
     1.7 - * Copyright (c) 2002 K A Fraser
     1.8 + * Copyright (c) 2002-2004 K A Fraser
     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 @@ -63,6 +63,9 @@ static void map_alloc(unsigned long firs
    1.13          ASSERT(!allocated_in_map(first_page + i));
    1.14  #endif
    1.15  
    1.16 +    memguard_unguard_range(phys_to_virt(first_page << PAGE_SHIFT), 
    1.17 +                           nr_pages << PAGE_SHIFT);
    1.18 +
    1.19      curr_idx  = first_page / PAGES_PER_MAPWORD;
    1.20      start_off = first_page & (PAGES_PER_MAPWORD-1);
    1.21      end_idx   = (first_page + nr_pages) / PAGES_PER_MAPWORD;
    1.22 @@ -92,6 +95,9 @@ static void map_free(unsigned long first
    1.23          ASSERT(allocated_in_map(first_page + i));
    1.24  #endif
    1.25  
    1.26 +    memguard_guard_range(phys_to_virt(first_page << PAGE_SHIFT), 
    1.27 +                         nr_pages << PAGE_SHIFT);
    1.28 +
    1.29      curr_idx = first_page / PAGES_PER_MAPWORD;
    1.30      start_off = first_page & (PAGES_PER_MAPWORD-1);
    1.31      end_idx   = (first_page + nr_pages) / PAGES_PER_MAPWORD;
    1.32 @@ -115,90 +121,13 @@ static void map_free(unsigned long first
    1.33   * BINARY BUDDY ALLOCATOR
    1.34   */
    1.35  
    1.36 -typedef struct chunk_head_st chunk_head_t;
    1.37 -
    1.38 -struct chunk_head_st {
    1.39 -    chunk_head_t  *next;
    1.40 -    chunk_head_t **pprev;
    1.41 -    int            level;
    1.42 -};
    1.43 -
    1.44  /* Linked lists of free chunks of different powers-of-two in size. */
    1.45 -#define FREELIST_SIZE ((sizeof(void*)<<3)-PAGE_SHIFT)
    1.46 -static chunk_head_t *free_head[FREELIST_SIZE];
    1.47 -static chunk_head_t  free_tail[FREELIST_SIZE];
    1.48 -#define FREELIST_EMPTY(_i) (free_head[_i] == &free_tail[i])
    1.49 +#define NR_ORDERS 11 /* Up to 2^10 pages can be allocated at once. */
    1.50 +static struct list_head free_head[NR_ORDERS];
    1.51  
    1.52  #define round_pgdown(_p)  ((_p)&PAGE_MASK)
    1.53  #define round_pgup(_p)    (((_p)+(PAGE_SIZE-1))&PAGE_MASK)
    1.54  
    1.55 -#ifdef MEMORY_GUARD
    1.56 -
    1.57 -/*
    1.58 - * Debug build: free memory chunks are made inaccessible.
    1.59 - */
    1.60 -
    1.61 -/* Make order-'o' pages inaccessible, from address 'p'. */
    1.62 -static inline void GUARD(void *p, int o)
    1.63 -{
    1.64 -    p = (void *)((unsigned long)p&PAGE_MASK);
    1.65 -    if ( p > (void *)&_end ) /* careful not to protect the 'free_tail' array */
    1.66 -        memguard_guard_range(p, (1<<(o+PAGE_SHIFT)));
    1.67 -}
    1.68 -
    1.69 -/* Make order-'o' pages accessible, from address 'p'. */
    1.70 -static inline void UNGUARD(void *p, int o)
    1.71 -{
    1.72 -    p = (void *)((unsigned long)p&PAGE_MASK);
    1.73 -    if ( p > (void *)&_end ) /* careful not to protect the 'free_tail' array */
    1.74 -        memguard_unguard_range(p, (1<<(o+PAGE_SHIFT)));
    1.75 -}
    1.76 -
    1.77 -/* Safe form of 'ch->level'. */
    1.78 -static inline int HEAD_LEVEL(chunk_head_t *ch)
    1.79 -{
    1.80 -    int l;
    1.81 -    ASSERT(memguard_is_guarded(ch));
    1.82 -    UNGUARD(ch, 0);
    1.83 -    l = ch->level;
    1.84 -    GUARD(ch, 0);
    1.85 -    return l;
    1.86 -}
    1.87 -
    1.88 -/* Safe form of '*ch->pprev = l'. */
    1.89 -static inline void UPDATE_PREV_FORWARDLINK(chunk_head_t *ch, chunk_head_t *l)
    1.90 -{
    1.91 -    ASSERT(((void *)ch->pprev < (void *)&_end) || 
    1.92 -           memguard_is_guarded(ch->pprev));
    1.93 -    UNGUARD(ch->pprev, 0);
    1.94 -    *ch->pprev = l;
    1.95 -    GUARD(ch->pprev, 0);
    1.96 -}
    1.97 -
    1.98 -/* Safe form of 'ch->next->pprev = l'. */
    1.99 -static inline void UPDATE_NEXT_BACKLINK(chunk_head_t *ch, chunk_head_t **l)
   1.100 -{
   1.101 -    ASSERT(((void *)ch->next < (void *)&_end) || 
   1.102 -           memguard_is_guarded(ch->next));
   1.103 -    UNGUARD(ch->next, 0);
   1.104 -    ch->next->pprev = l;
   1.105 -    GUARD(ch->next, 0);
   1.106 -}
   1.107 -
   1.108 -#else
   1.109 -
   1.110 -/*
   1.111 - * Non-debug build: free memory chunks are not made inaccessible.
   1.112 - */
   1.113 -
   1.114 -#define GUARD(_p,_o) ((void)0)
   1.115 -#define UNGUARD(_p,_o) ((void)0)
   1.116 -#define HEAD_LEVEL(_ch) ((_ch)->level)
   1.117 -#define UPDATE_PREV_FORWARDLINK(_ch,_link) (*(_ch)->pprev = (_link))
   1.118 -#define UPDATE_NEXT_BACKLINK(_ch,_link) ((_ch)->next->pprev = (_link))
   1.119 -
   1.120 -#endif
   1.121 -
   1.122  
   1.123  /*
   1.124   * Initialise allocator, placing addresses [@min,@max] in free pool.
   1.125 @@ -207,15 +136,11 @@ static inline void UPDATE_NEXT_BACKLINK(
   1.126  void __init init_page_allocator(unsigned long min, unsigned long max)
   1.127  {
   1.128      int i;
   1.129 -    unsigned long range, bitmap_size, p, remaining;
   1.130 -    chunk_head_t *ch;
   1.131 +    unsigned long range, bitmap_size;
   1.132 +    struct pfn_info *pg;
   1.133  
   1.134 -    for ( i = 0; i < FREELIST_SIZE; i++ )
   1.135 -    {
   1.136 -        free_head[i]       = &free_tail[i];
   1.137 -        free_tail[i].pprev = &free_head[i];
   1.138 -        free_tail[i].next  = NULL;
   1.139 -    }
   1.140 +    for ( i = 0; i < NR_ORDERS; i++ )
   1.141 +        INIT_LIST_HEAD(&free_head[i]);
   1.142  
   1.143      min = round_pgup  (min);
   1.144      max = round_pgdown(max);
   1.145 @@ -232,33 +157,24 @@ void __init init_page_allocator(unsigned
   1.146      /* Free up the memory we've been given to play with. */
   1.147      map_free(min>>PAGE_SHIFT, range>>PAGE_SHIFT);
   1.148      
   1.149 -    /* The buddy lists are addressed in high memory. */
   1.150 -    min += PAGE_OFFSET;
   1.151 -    max += PAGE_OFFSET;
   1.152 -
   1.153 -    p         = min;
   1.154 -    remaining = range;
   1.155 -    while ( remaining != 0 )
   1.156 +    pg = &frame_table[min >> PAGE_SHIFT];
   1.157 +    while ( range != 0 )
   1.158      {
   1.159          /*
   1.160 -         * Next chunk is limited by alignment of p, but also must not be bigger
   1.161 -         * than remaining bytes.
   1.162 +         * Next chunk is limited by alignment of pg, but also must not be
   1.163 +         * bigger than remaining bytes.
   1.164           */
   1.165 -        for ( i = PAGE_SHIFT; (1<<(i+1)) <= remaining; i++ )
   1.166 -            if ( p & (1<<i) ) break;
   1.167 +        for ( i = 0; i < NR_ORDERS; i++ )
   1.168 +            if ( ((page_to_pfn(pg) & (1 << i)) != 0) ||
   1.169 +                 ((1 << (i + PAGE_SHIFT + 1)) > range) )
   1.170 +                break;
   1.171  
   1.172 -        ch = (chunk_head_t *)p;
   1.173 -        p         += (1<<i);
   1.174 -        remaining -= (1<<i);
   1.175 -        i -= PAGE_SHIFT;
   1.176 -        ch->level       = i;
   1.177 -        ch->next        = free_head[i];
   1.178 -        ch->pprev       = &free_head[i];
   1.179 -        ch->next->pprev = &ch->next;
   1.180 -        free_head[i]    = ch;
   1.181 +        PFN_ORDER(pg) = i;
   1.182 +        list_add_tail(&pg->list, &free_head[i]);
   1.183 +
   1.184 +        pg    += 1 << i;
   1.185 +        range -= 1 << (i + PAGE_SHIFT);
   1.186      }
   1.187 -
   1.188 -    memguard_guard_range((void *)min, range);
   1.189  }
   1.190  
   1.191  
   1.192 @@ -266,55 +182,36 @@ void __init init_page_allocator(unsigned
   1.193  unsigned long alloc_xenheap_pages(int order)
   1.194  {
   1.195      int i, attempts = 0;
   1.196 -    chunk_head_t *alloc_ch, *spare_ch;
   1.197 -    unsigned long           flags;
   1.198 +    struct pfn_info *pg;
   1.199 +    unsigned long flags;
   1.200  
   1.201  retry:
   1.202      spin_lock_irqsave(&alloc_lock, flags);
   1.203  
   1.204      /* Find smallest order which can satisfy the request. */
   1.205 -    for ( i = order; i < FREELIST_SIZE; i++ )
   1.206 -	if ( !FREELIST_EMPTY(i) ) 
   1.207 +    for ( i = order; i < NR_ORDERS; i++ )
   1.208 +	if ( !list_empty(&free_head[i]) )
   1.209  	    break;
   1.210  
   1.211 -    if ( i == FREELIST_SIZE ) 
   1.212 +    if ( i == NR_ORDERS ) 
   1.213          goto no_memory;
   1.214   
   1.215 -    /* Unlink a chunk. */
   1.216 -    alloc_ch = free_head[i];
   1.217 -    UNGUARD(alloc_ch, i);
   1.218 -    free_head[i] = alloc_ch->next;
   1.219 -    /* alloc_ch->next->pprev = alloc_ch->pprev */
   1.220 -    UPDATE_NEXT_BACKLINK(alloc_ch, alloc_ch->pprev);
   1.221 +    pg = list_entry(free_head[i].next, struct pfn_info, list);
   1.222 +    list_del(&pg->list);
   1.223  
   1.224 -    /* We may have to break the chunk a number of times. */
   1.225 +    /* We may have to halve the chunk a number of times. */
   1.226      while ( i != order )
   1.227      {
   1.228 -        /* Split into two equal parts. */
   1.229 -        i--;
   1.230 -        spare_ch = (chunk_head_t *)((char *)alloc_ch + (1<<(i+PAGE_SHIFT)));
   1.231 -
   1.232 -        /* Create new header for spare chunk. */
   1.233 -        spare_ch->level = i;
   1.234 -        spare_ch->next  = free_head[i];
   1.235 -        spare_ch->pprev = &free_head[i];
   1.236 -
   1.237 -        /* Link in the spare chunk. */
   1.238 -        /* spare_ch->next->pprev = &spare_ch->next */
   1.239 -        UPDATE_NEXT_BACKLINK(spare_ch, &spare_ch->next);
   1.240 -        free_head[i] = spare_ch;
   1.241 -        GUARD(spare_ch, i);
   1.242 +        PFN_ORDER(pg) = --i;
   1.243 +        list_add_tail(&pg->list, &free_head[i]);
   1.244 +        pg += 1 << i;
   1.245      }
   1.246      
   1.247 -    map_alloc(virt_to_phys(alloc_ch)>>PAGE_SHIFT, 1<<order);
   1.248 +    map_alloc(page_to_pfn(pg), 1<<order);
   1.249  
   1.250      spin_unlock_irqrestore(&alloc_lock, flags);
   1.251  
   1.252 -#ifdef MEMORY_GUARD
   1.253 -    memset(alloc_ch, 0x55, 1 << (order + PAGE_SHIFT));
   1.254 -#endif
   1.255 -
   1.256 -    return((unsigned long)alloc_ch);
   1.257 +    return (unsigned long)page_to_virt(pg);
   1.258  
   1.259   no_memory:
   1.260      spin_unlock_irqrestore(&alloc_lock, flags);
   1.261 @@ -335,63 +232,42 @@ retry:
   1.262  /* Free 2^@order pages at VIRTUAL address @p. */
   1.263  void free_xenheap_pages(unsigned long p, int order)
   1.264  {
   1.265 -    unsigned long size = 1 << (order + PAGE_SHIFT);
   1.266 -    chunk_head_t *ch;
   1.267 +    unsigned long mask;
   1.268 +    struct pfn_info *pg = virt_to_page(p);
   1.269      unsigned long flags;
   1.270 -    unsigned long pfn = virt_to_phys((void *)p) >> PAGE_SHIFT;
   1.271  
   1.272      spin_lock_irqsave(&alloc_lock, flags);
   1.273  
   1.274 -#ifdef MEMORY_GUARD
   1.275 -    memset((void *)p, 0xaa, size);
   1.276 -#endif
   1.277 -
   1.278 -    map_free(pfn, 1<<order);
   1.279 +    map_free(page_to_pfn(pg), 1<<order);
   1.280      
   1.281      /* Merge chunks as far as possible. */
   1.282      for ( ; ; )
   1.283      {
   1.284 -        if ( (p & size) )
   1.285 +        mask = 1 << order;
   1.286 +
   1.287 +        if ( (page_to_pfn(pg) & mask) )
   1.288          {
   1.289              /* Merge with predecessor block? */
   1.290 -            if ( allocated_in_map(pfn-(1<<order)) )
   1.291 +            if ( allocated_in_map(page_to_pfn(pg)-mask) ||
   1.292 +                 (PFN_ORDER(pg-mask) != order) )
   1.293                  break;
   1.294 -            ch = (chunk_head_t *)(p - size);
   1.295 -            if ( HEAD_LEVEL(ch) != order )
   1.296 -                break;
   1.297 -            p   -= size;
   1.298 -            pfn -= 1<<order;
   1.299 +            list_del(&(pg-mask)->list);
   1.300 +            pg -= mask;
   1.301          }
   1.302          else
   1.303          {
   1.304              /* Merge with successor block? */
   1.305 -            if ( allocated_in_map(pfn+(1<<order)) )
   1.306 +            if ( allocated_in_map(page_to_pfn(pg)+mask) ||
   1.307 +                 (PFN_ORDER(pg+mask) != order) )
   1.308                  break;
   1.309 -            ch = (chunk_head_t *)(p + size);
   1.310 -            if ( HEAD_LEVEL(ch) != order )
   1.311 -                break;
   1.312 +            list_del(&(pg+mask)->list);
   1.313          }
   1.314          
   1.315 -        /* Okay, unlink the neighbour. */
   1.316 -        UNGUARD(ch, order);
   1.317 -        /* *ch->pprev = ch->next */
   1.318 -        UPDATE_PREV_FORWARDLINK(ch, ch->next);
   1.319 -        /* ch->next->pprev = ch->pprev */
   1.320 -        UPDATE_NEXT_BACKLINK(ch, ch->pprev);
   1.321 -
   1.322          order++;
   1.323 -        size <<= 1;
   1.324      }
   1.325  
   1.326 -    /* Okay, add the final chunk to the appropriate free list. */
   1.327 -    ch = (chunk_head_t *)p;
   1.328 -    ch->level = order;
   1.329 -    ch->pprev = &free_head[order];
   1.330 -    ch->next  = free_head[order];
   1.331 -    /* ch->next->pprev = &ch->next */
   1.332 -    UPDATE_NEXT_BACKLINK(ch, &ch->next);
   1.333 -    free_head[order] = ch;
   1.334 -    GUARD(ch, order);
   1.335 +    PFN_ORDER(pg) = order;
   1.336 +    list_add_tail(&pg->list, &free_head[order]);
   1.337  
   1.338      spin_unlock_irqrestore(&alloc_lock, flags);
   1.339  }