l4/pkg/valgrind/src/valgrind-3.6.0-svn/drd/drd_bitmap2_node.c

   1 /* -*- mode: C; c-basic-offset: 3; indent-tabs-mode: nil; -*- */
   2 /*
   3   This file is part of drd, a thread error detector.
   4
   5   Copyright (C) 2006-2011 Bart Van Assche <bvanassche@acm.org>.
   6
   7   This program is free software; you can redistribute it and/or
   8   modify it under the terms of the GNU General Public License as
   9   published by the Free Software Foundation; either version 2 of the
  10   License, or (at your option) any later version.
  11
  12   This program is distributed in the hope that it will be useful, but
  13   WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15   General Public License for more details.
  16
  17   You should have received a copy of the GNU General Public License
  18   along with this program; if not, write to the Free Software
  19   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  20   02111-1307, USA.
  21
  22   The GNU General Public License is contained in the file COPYING.
  23 */
  24
  25 /*
  26  * Block allocator for second-level bitmap nodes. Each node consists of
  27  * an OSetGen node and a struct bitmap2. The code below allocates
  28  * NODES_PER_CHUNK nodes at a time.
  29  */
  30
  31
  32 #include "drd_basics.h"           /* DRD_() */
  33 #include "drd_bitmap.h"           /* struct bitmap2 */
  34 #include "pub_drd_bitmap.h"
  35 #include "pub_tool_basics.h"      /* Addr, SizeT */
  36 #include "pub_tool_libcassert.h"  /* tl_assert() */
  37 #include "pub_tool_libcbase.h"    /* VG_ROUNDUP() */
  38 #include "pub_tool_libcprint.h"   /* VG_(message)() */
  39 #include "pub_tool_mallocfree.h"  /* VG_(malloc), VG_(free) */
  40
  41
  42 #define NODES_PER_CHUNCK 512
  43
  44
  45 /* Local type definitions. */
  46
  47 struct block_allocator_chunk {
  48    struct block_allocator_chunk* next;
  49    struct block_allocator_chunk* prev;
  50    int   nallocated;
  51    void* data;
  52    void* data_end;
  53    void* first_free;
  54 };
  55
  56
  57 /* Local variables. */
  58
  59 static SizeT s_bm2_node_size;
  60 static struct block_allocator_chunk* s_first;
  61
  62
  63 /* Function definitions. */
  64
  65 /**
  66  * Allocate a new chunk and insert it at the start of the doubly-linked list
  67  * s_first.
  68  */
  69 static struct block_allocator_chunk* allocate_new_chunk(void)
  70 {
  71    struct block_allocator_chunk* p;
  72    int i;
  73
  74    tl_assert(s_bm2_node_size > 0);
  75
  76    p = VG_(malloc)("drd.bitmap.bac",
  77                    sizeof(*p) + NODES_PER_CHUNCK * s_bm2_node_size);
  78    tl_assert(p);
  79    p->next = s_first;
  80    if (s_first)
  81       p->next->prev = p;
  82    s_first = p;
  83    p->prev = 0;
  84    p->nallocated = 0;
  85    p->data = (char*)p + sizeof(*p);
  86    tl_assert(p->data);
  87    p->data_end = (char*)(p->data) + NODES_PER_CHUNCK * s_bm2_node_size;
  88    p->first_free = p->data;
  89    for (i = 0; i < NODES_PER_CHUNCK - 1; i++)
  90    {
  91       *(void**)((char*)(p->data) + i * s_bm2_node_size)
  92          = (char*)(p->data) + (i + 1) * s_bm2_node_size;
  93    }
  94    tl_assert(i == NODES_PER_CHUNCK - 1);
  95    *(void**)((char*)(p->data) + i * s_bm2_node_size) = NULL;
  96
  97    return p;
  98 }
  99
 100 /** Free a chunk and remove it from the list of chunks. */
 101 static void free_chunk(struct block_allocator_chunk* const p)
 102 {
 103    tl_assert(p);
 104    tl_assert(p->nallocated == 0);
 105
 106    if (p == s_first)
 107       s_first = p->next;
 108    else if (p->prev)
 109       p->prev->next = p->next;
 110    if (p->next)
 111       p->next->prev = p->prev;
 112    VG_(free)(p);
 113 }
 114
 115 /** Allocate a node. */
 116 void* DRD_(bm2_alloc_node)(HChar* const ec, const SizeT szB)
 117 {
 118    /*
 119     * If szB < sizeof(struct bitmap2) then this function has been called to
 120     * allocate an AVL tree root node. Otherwise it has been called to allocate
 121     * an AVL tree branch or leaf node.
 122     */
 123    if (szB < sizeof(struct bitmap2))
 124       return VG_(malloc)(ec, szB);
 125
 126    while (True)
 127    {
 128       struct block_allocator_chunk* p;
 129
 130       if (s_bm2_node_size == 0)
 131          s_bm2_node_size = szB;
 132       else
 133          tl_assert(s_bm2_node_size == szB);
 134
 135       for (p = s_first; p; p = p->next)
 136       {
 137          if (p->first_free)
 138          {
 139             void* result;
 140
 141             p->nallocated++;
 142             result = p->first_free;
 143             p->first_free = *(void**)(p->first_free);
 144             return result;
 145          }
 146       }
 147
 148       allocate_new_chunk();
 149    }
 150 }
 151
 152 /** Free a node. */
 153 void  DRD_(bm2_free_node)(void* const bm2)
 154 {
 155    struct block_allocator_chunk* p;
 156
 157    tl_assert(bm2);
 158
 159    if (s_bm2_node_size > 0) {
 160       for (p = s_first; p; p = p->next) {
 161          if (p->data <= bm2 && bm2 < p->data_end) {
 162             /* Free a non-root AVL tree node. */
 163             tl_assert(((char*)bm2 - (char*)(p->data)) % s_bm2_node_size == 0);
 164             *(void**)bm2 = p->first_free;
 165             p->first_free = bm2;
 166             tl_assert(p->nallocated >= 1);
 167             if (--(p->nallocated) == 0)
 168                free_chunk(p);
 169             return;
 170          }
 171       }
 172    }
 173    /* Free the memory that was allocated for an AVL tree root node. */
 174    VG_(free)(bm2);
 175 }