← Back to branch summary

~bkerensa/ubuntu/raring/valgrind/merge-from-deb

« back to all changes in this revision

Viewing changes to drd/drd_bitmap2_node.c

  • Committer: Benjamin Kerensa
  • Date: 2012-11-21 23:57:58 UTC
  • mfrom: (1.1.16)
  • Revision ID: bkerensa@ubuntu.com-20121121235758-bd1rv5uc5vzov2p6
Merge from debian unstable

Show diffs side-by-side

added added

removed removed

Lines of Context:
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_root_node_size;
60
 
static SizeT s_bm2_node_size;
61
 
static struct block_allocator_chunk* s_first;
62
 
 
63
 
 
64
 
/* Function definitions. */
65
 
 
66
 
/**
67
 
 * Allocate a new chunk and insert it at the start of the doubly-linked list
68
 
 * s_first.
69
 
 */
70
 
static struct block_allocator_chunk* allocate_new_chunk(void)
71
 
{
72
 
   struct block_allocator_chunk* p;
73
 
   int i;
74
 
 
75
 
   tl_assert(s_bm2_node_size > 0);
76
 
 
77
 
   p = VG_(malloc)("drd.bitmap.bac",
78
 
                   sizeof(*p) + NODES_PER_CHUNCK * s_bm2_node_size);
79
 
   tl_assert(p);
80
 
   p->next = s_first;
81
 
   if (s_first)
82
 
      p->next->prev = p;
83
 
   s_first = p;
84
 
   p->prev = 0;
85
 
   p->nallocated = 0;
86
 
   p->data = (char*)p + sizeof(*p);
87
 
   tl_assert(p->data);
88
 
   p->data_end = (char*)(p->data) + NODES_PER_CHUNCK * s_bm2_node_size;
89
 
   p->first_free = p->data;
90
 
   for (i = 0; i < NODES_PER_CHUNCK - 1; i++)
91
 
   {
92
 
      *(void**)((char*)(p->data) + i * s_bm2_node_size)
93
 
         = (char*)(p->data) + (i + 1) * s_bm2_node_size;
94
 
   }
95
 
   tl_assert(i == NODES_PER_CHUNCK - 1);
96
 
   *(void**)((char*)(p->data) + i * s_bm2_node_size) = NULL;
97
 
 
98
 
   return p;
99
 
}
100
 
 
101
 
/** Free a chunk and remove it from the list of chunks. */
102
 
static void free_chunk(struct block_allocator_chunk* const p)
103
 
{
104
 
   tl_assert(p);
105
 
   tl_assert(p->nallocated == 0);
106
 
 
107
 
   if (p == s_first)
108
 
      s_first = p->next;
109
 
   else if (p->prev)
110
 
      p->prev->next = p->next;
111
 
   if (p->next)
112
 
      p->next->prev = p->prev;
113
 
   VG_(free)(p);
114
 
}
115
 
 
116
 
/** Allocate a node. */
117
 
void* DRD_(bm2_alloc_node)(HChar* const ec, const SizeT szB)
118
 
{
119
 
   /*
120
 
    * If szB < sizeof(struct bitmap2) then this function has been called to
121
 
    * allocate an AVL tree root node. Otherwise it has been called to allocate
122
 
    * an AVL tree branch or leaf node.
123
 
    */
124
 
   if (s_root_node_size == 0)
125
 
      s_root_node_size = szB;
126
 
   if (szB == s_root_node_size)
127
 
      return VG_(malloc)(ec, szB);
128
 
 
129
 
   while (True)
130
 
   {
131
 
      struct block_allocator_chunk* p;
132
 
 
133
 
      if (s_bm2_node_size == 0)
134
 
         s_bm2_node_size = szB;
135
 
      else
136
 
         tl_assert(s_bm2_node_size == szB);
137
 
 
138
 
      for (p = s_first; p; p = p->next)
139
 
      {
140
 
         if (p->first_free)
141
 
         {
142
 
            void* result;
143
 
 
144
 
            p->nallocated++;
145
 
            result = p->first_free;
146
 
            p->first_free = *(void**)(p->first_free);
147
 
            return result;
148
 
         }
149
 
      }
150
 
 
151
 
      allocate_new_chunk();
152
 
   }
153
 
}
154
 
 
155
 
/** Free a node. */
156
 
void  DRD_(bm2_free_node)(void* const bm2)
157
 
{
158
 
   struct block_allocator_chunk* p;
159
 
 
160
 
   tl_assert(bm2);
161
 
 
162
 
   if (s_bm2_node_size > 0) {
163
 
      for (p = s_first; p; p = p->next) {
164
 
         if (p->data <= bm2 && bm2 < p->data_end) {
165
 
            /* Free a non-root AVL tree node. */
166
 
            tl_assert(((char*)bm2 - (char*)(p->data)) % s_bm2_node_size == 0);
167
 
            *(void**)bm2 = p->first_free;
168
 
            p->first_free = bm2;
169
 
            tl_assert(p->nallocated >= 1);
170
 
            if (--(p->nallocated) == 0)
171
 
               free_chunk(p);
172
 
            return;
173
 
         }
174
 
      }
175
 
   }
176
 
   /* Free the memory that was allocated for an AVL tree root node. */
177
 
   VG_(free)(bm2);
178
 
}