drivers/net/sfc/sfc_resource/buddy.c

   1
   2 /****************************************************************************
   3  * Driver for Solarflare network controllers -
   4  *          resource management for Xen backend, OpenOnload, etc
   5  *           (including support for SFE4001 10GBT NIC)
   6  *
   7  * This file contains implementation of a buddy allocator.
   8  *
   9  * Copyright 2005-2007: Solarflare Communications Inc,
  10  *                      9501 Jeronimo Road, Suite 250,
  11  *                      Irvine, CA 92618, USA
  12  *
  13  * Developed and maintained by Solarflare Communications:
  14  *                      <linux-xen-drivers@solarflare.com>
  15  *                      <onload-dev@solarflare.com>
  16  *
  17  * Certain parts of the driver were implemented by
  18  *          Alexandra Kossovsky <Alexandra.Kossovsky@oktetlabs.ru>
  19  *          OKTET Labs Ltd, Russia,
  20  *          http://oktetlabs.ru, <info@oktetlabs.ru>
  21  *          by request of Solarflare Communications
  22  *
  23  *
  24  * This program is free software; you can redistribute it and/or modify it
  25  * under the terms of the GNU General Public License version 2 as published
  26  * by the Free Software Foundation, incorporated herein by reference.
  27  *
  28  * This program is distributed in the hope that it will be useful,
  29  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  30  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31  * GNU General Public License for more details.
  32  *
  33  * You should have received a copy of the GNU General Public License
  34  * along with this program; if not, write to the Free Software
  35  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  36  ****************************************************************************
  37  */
  38
  39 #include <ci/efhw/common.h> /* get uintXX types on win32 */
  40 #include <ci/efrm/sysdep.h>
  41 #include <ci/efrm/buddy.h>
  42 #include <ci/efrm/debug.h>
  43
  44 #if 1
  45 #define DEBUG_ALLOC(x)
  46 #else
  47 #define DEBUG_ALLOC(x) x
  48
  49 static inline void efrm_buddy_dump(struct efrm_buddy_allocator *b)
  50 {
  51         unsigned o;
  52
  53         EFRM_NOTICE("%s: dump allocator with order %u",
  54                     __func__, b->order);
  55         for (o = 0; o <= b->order; o++) {
  56                 struct list_head *l = &b->free_lists[o];
  57                 while (l->next != &b->free_lists[o]) {
  58                         l = l->next;
  59                         EFRM_NOTICE("%s: order %x: %zx", __func__, o,
  60                                     l - b->links);
  61                 }
  62         }
  63 }
  64 #endif
  65
  66 /*
  67  * The purpose of the following inline functions is to give the
  68  * understandable names to the simple actions.
  69  */
  70 static inline void
  71 efrm_buddy_free_list_add(struct efrm_buddy_allocator *b,
  72                          unsigned order, unsigned addr)
  73 {
  74         list_add(&b->links[addr], &b->free_lists[order]);
  75         b->orders[addr] = (uint8_t) order;
  76 }
  77 static inline void
  78 efrm_buddy_free_list_del(struct efrm_buddy_allocator *b, unsigned addr)
  79 {
  80         list_del(&b->links[addr]);
  81         b->links[addr].next = NULL;
  82 }
  83 static inline int
  84 efrm_buddy_free_list_empty(struct efrm_buddy_allocator *b, unsigned order)
  85 {
  86         return list_empty(&b->free_lists[order]);
  87 }
  88 static inline unsigned
  89 efrm_buddy_free_list_pop(struct efrm_buddy_allocator *b, unsigned order)
  90 {
  91         struct list_head *l = list_pop(&b->free_lists[order]);
  92         l->next = NULL;
  93         return (unsigned)(l - b->links);
  94 }
  95 static inline int
  96 efrm_buddy_addr_in_free_list(struct efrm_buddy_allocator *b, unsigned addr)
  97 {
  98         return b->links[addr].next != NULL;
  99 }
 100 static inline unsigned
 101 efrm_buddy_free_list_first(struct efrm_buddy_allocator *b, unsigned order)
 102 {
 103         return (unsigned)(b->free_lists[order].next - b->links);
 104 }
 105
 106 int efrm_buddy_ctor(struct efrm_buddy_allocator *b, unsigned order)
 107 {
 108         unsigned o;
 109         unsigned size = 1 << order;
 110
 111         DEBUG_ALLOC(EFRM_NOTICE("%s(%u)", __func__, order));
 112         EFRM_ASSERT(b);
 113         EFRM_ASSERT(order <= sizeof(unsigned) * 8 - 1);
 114
 115         b->order = order;
 116         b->free_lists = vmalloc((order + 1) * sizeof(struct list_head));
 117         if (b->free_lists == NULL)
 118                 goto fail1;
 119
 120         b->links = vmalloc(size * sizeof(struct list_head));
 121         if (b->links == NULL)
 122                 goto fail2;
 123
 124         b->orders = vmalloc(size);
 125         if (b->orders == NULL)
 126                 goto fail3;
 127
 128         memset(b->links, 0, size * sizeof(struct list_head));
 129
 130         for (o = 0; o <= b->order; ++o)
 131                 INIT_LIST_HEAD(b->free_lists + o);
 132
 133         efrm_buddy_free_list_add(b, b->order, 0);
 134
 135         return 0;
 136
 137 fail3:
 138         vfree(b->links);
 139 fail2:
 140         vfree(b->free_lists);
 141 fail1:
 142         return -ENOMEM;
 143 }
 144
 145 void efrm_buddy_dtor(struct efrm_buddy_allocator *b)
 146 {
 147         EFRM_ASSERT(b);
 148
 149         vfree(b->free_lists);
 150         vfree(b->links);
 151         vfree(b->orders);
 152 }
 153
 154 int efrm_buddy_alloc(struct efrm_buddy_allocator *b, unsigned order)
 155 {
 156         unsigned smallest;
 157         unsigned addr;
 158
 159         DEBUG_ALLOC(EFRM_NOTICE("%s(%u)", __func__, order));
 160         EFRM_ASSERT(b);
 161
 162         /* Find smallest chunk that is big enough.  ?? Can optimise this by
 163          ** keeping array of pointers to smallest chunk for each order.
 164          */
 165         smallest = order;
 166         while (smallest <= b->order &&
 167                efrm_buddy_free_list_empty(b, smallest))
 168                 ++smallest;
 169
 170         if (smallest > b->order) {
 171                 DEBUG_ALLOC(EFRM_NOTICE
 172                             ("buddy - alloc order %d failed - max order %d",
 173                              order, b->order););
 174                 return -ENOMEM;
 175         }
 176
 177         /* Split blocks until we get one of the correct size. */
 178         addr = efrm_buddy_free_list_pop(b, smallest);
 179
 180         DEBUG_ALLOC(EFRM_NOTICE("buddy - alloc %x order %d cut from order %d",
 181                                 addr, order, smallest););
 182         while (smallest-- > order)
 183                 efrm_buddy_free_list_add(b, smallest, addr + (1 << smallest));
 184
 185         EFRM_DO_DEBUG(b->orders[addr] = (uint8_t) order);
 186
 187         EFRM_ASSERT(addr < 1u << b->order);
 188         return addr;
 189 }
 190
 191 void
 192 efrm_buddy_free(struct efrm_buddy_allocator *b, unsigned addr,
 193                 unsigned order)
 194 {
 195         unsigned buddy_addr;
 196
 197         DEBUG_ALLOC(EFRM_NOTICE("%s(%u, %u)", __func__, addr, order));
 198         EFRM_ASSERT(b);
 199         EFRM_ASSERT(order <= b->order);
 200         EFRM_ASSERT((unsigned long)addr + ((unsigned long)1 << order) <=
 201                     (unsigned long)1 << b->order);
 202         EFRM_ASSERT(!efrm_buddy_addr_in_free_list(b, addr));
 203         EFRM_ASSERT(b->orders[addr] == order);
 204
 205         /* merge free blocks */
 206         while (order < b->order) {
 207                 buddy_addr = addr ^ (1 << order);
 208                 if (!efrm_buddy_addr_in_free_list(b, buddy_addr) ||
 209                     b->orders[buddy_addr] != order)
 210                         break;
 211                 efrm_buddy_free_list_del(b, buddy_addr);
 212                 if (buddy_addr < addr)
 213                         addr = buddy_addr;
 214                 ++order;
 215         }
 216
 217         DEBUG_ALLOC(EFRM_NOTICE
 218                     ("buddy - free %x merged into order %d", addr, order););
 219         efrm_buddy_free_list_add(b, order, addr);
 220 }