← Back to branch summary

~ubuntu-branches/ubuntu/trusty/mariadb-5.5/trusty-proposed

« back to all changes in this revision

Viewing changes to extra/jemalloc/include/jemalloc/internal/bitmap.h

  • Committer: Package Import Robot
  • Author(s): James Page, Otto Kekäläinen
  • Date: 2014-02-17 16:51:52 UTC
  • mfrom: (2.1.1 sid)
  • Revision ID: package-import@ubuntu.com-20140217165152-k315d3175g865kkx
Tags: 5.5.35-1
http://bugs.debian.org/737597
http://bugs.debian.org/733002
http://bugs.debian.org/734426
http://bugs.debian.org/735284
http://bugs.debian.org/736480
http://bugs.debian.org/732967
[ Otto Kekäläinen ]
* New upstream release, fixing the following security issues:
  - Buffer overflow in client/mysql.cc (Closes: #737597).
    - CVE-2014-0001
  - http://www.oracle.com/technetwork/topics/security/cpujan2014-1972949.html
    - CVE-2013-5891
    - CVE-2013-5908
    - CVE-2014-0386
    - CVE-2014-0393
    - CVE-2014-0401
    - CVE-2014-0402
    - CVE-2014-0412
    - CVE-2014-0420
    - CVE-2014-0437
* Upstream https://mariadb.atlassian.net/browse/MDEV-4902
  fixes compatibility with Bison 3.0 (Closes: #733002)
* Updated Russian debconf translation (Closes: #734426)
* Updated Japanese debconf translation (Closes: #735284)
* Updated French debconf translation (Closes: #736480)
* Renamed SONAME properly (Closes: #732967)

Show diffs side-by-side

added added

removed removed

Lines of Context:
extra/jemalloc/include/jemalloc/internal/bitmap.h
 
1
/******************************************************************************/
 
2
#ifdef JEMALLOC_H_TYPES
 
3
 
 
4
/* Maximum bitmap bit count is 2^LG_BITMAP_MAXBITS. */
 
5
#define LG_BITMAP_MAXBITS       LG_RUN_MAXREGS
 
6
 
 
7
typedef struct bitmap_level_s bitmap_level_t;
 
8
typedef struct bitmap_info_s bitmap_info_t;
 
9
typedef unsigned long bitmap_t;
 
10
#define LG_SIZEOF_BITMAP        LG_SIZEOF_LONG
 
11
 
 
12
/* Number of bits per group. */
 
13
#define LG_BITMAP_GROUP_NBITS           (LG_SIZEOF_BITMAP + 3)
 
14
#define BITMAP_GROUP_NBITS              (ZU(1) << LG_BITMAP_GROUP_NBITS)
 
15
#define BITMAP_GROUP_NBITS_MASK         (BITMAP_GROUP_NBITS-1)
 
16
 
 
17
/* Maximum number of levels possible. */
 
18
#define BITMAP_MAX_LEVELS                                               \
 
19
    (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP)                              \
 
20
    + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP)
 
21
 
 
22
#endif /* JEMALLOC_H_TYPES */
 
23
/******************************************************************************/
 
24
#ifdef JEMALLOC_H_STRUCTS
 
25
 
 
26
struct bitmap_level_s {
 
27
        /* Offset of this level's groups within the array of groups. */
 
28
        size_t group_offset;
 
29
};
 
30
 
 
31
struct bitmap_info_s {
 
32
        /* Logical number of bits in bitmap (stored at bottom level). */
 
33
        size_t nbits;
 
34
 
 
35
        /* Number of levels necessary for nbits. */
 
36
        unsigned nlevels;
 
37
 
 
38
        /*
 
39
         * Only the first (nlevels+1) elements are used, and levels are ordered
 
40
         * bottom to top (e.g. the bottom level is stored in levels[0]).
 
41
         */
 
42
        bitmap_level_t levels[BITMAP_MAX_LEVELS+1];
 
43
};
 
44
 
 
45
#endif /* JEMALLOC_H_STRUCTS */
 
46
/******************************************************************************/
 
47
#ifdef JEMALLOC_H_EXTERNS
 
48
 
 
49
void    bitmap_info_init(bitmap_info_t *binfo, size_t nbits);
 
50
size_t  bitmap_info_ngroups(const bitmap_info_t *binfo);
 
51
size_t  bitmap_size(size_t nbits);
 
52
void    bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo);
 
53
 
 
54
#endif /* JEMALLOC_H_EXTERNS */
 
55
/******************************************************************************/
 
56
#ifdef JEMALLOC_H_INLINES
 
57
 
 
58
#ifndef JEMALLOC_ENABLE_INLINE
 
59
bool    bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo);
 
60
bool    bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
 
61
void    bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
 
62
size_t  bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo);
 
63
void    bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
 
64
#endif
 
65
 
 
66
#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_))
 
67
JEMALLOC_INLINE bool
 
68
bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo)
 
69
{
 
70
        unsigned rgoff = binfo->levels[binfo->nlevels].group_offset - 1;
 
71
        bitmap_t rg = bitmap[rgoff];
 
72
        /* The bitmap is full iff the root group is 0. */
 
73
        return (rg == 0);
 
74
}
 
75
 
 
76
JEMALLOC_INLINE bool
 
77
bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
 
78
{
 
79
        size_t goff;
 
80
        bitmap_t g;
 
81
 
 
82
        assert(bit < binfo->nbits);
 
83
        goff = bit >> LG_BITMAP_GROUP_NBITS;
 
84
        g = bitmap[goff];
 
85
        return (!(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))));
 
86
}
 
87
 
 
88
JEMALLOC_INLINE void
 
89
bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
 
90
{
 
91
        size_t goff;
 
92
        bitmap_t *gp;
 
93
        bitmap_t g;
 
94
 
 
95
        assert(bit < binfo->nbits);
 
96
        assert(bitmap_get(bitmap, binfo, bit) == false);
 
97
        goff = bit >> LG_BITMAP_GROUP_NBITS;
 
98
        gp = &bitmap[goff];
 
99
        g = *gp;
 
100
        assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)));
 
101
        g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
 
102
        *gp = g;
 
103
        assert(bitmap_get(bitmap, binfo, bit));
 
104
        /* Propagate group state transitions up the tree. */
 
105
        if (g == 0) {
 
106
                unsigned i;
 
107
                for (i = 1; i < binfo->nlevels; i++) {
 
108
                        bit = goff;
 
109
                        goff = bit >> LG_BITMAP_GROUP_NBITS;
 
110
                        gp = &bitmap[binfo->levels[i].group_offset + goff];
 
111
                        g = *gp;
 
112
                        assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)));
 
113
                        g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
 
114
                        *gp = g;
 
115
                        if (g != 0)
 
116
                                break;
 
117
                }
 
118
        }
 
119
}
 
120
 
 
121
/* sfu: set first unset. */
 
122
JEMALLOC_INLINE size_t
 
123
bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo)
 
124
{
 
125
        size_t bit;
 
126
        bitmap_t g;
 
127
        unsigned i;
 
128
 
 
129
        assert(bitmap_full(bitmap, binfo) == false);
 
130
 
 
131
        i = binfo->nlevels - 1;
 
132
        g = bitmap[binfo->levels[i].group_offset];
 
133
        bit = ffsl(g) - 1;
 
134
        while (i > 0) {
 
135
                i--;
 
136
                g = bitmap[binfo->levels[i].group_offset + bit];
 
137
                bit = (bit << LG_BITMAP_GROUP_NBITS) + (ffsl(g) - 1);
 
138
        }
 
139
 
 
140
        bitmap_set(bitmap, binfo, bit);
 
141
        return (bit);
 
142
}
 
143
 
 
144
JEMALLOC_INLINE void
 
145
bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
 
146
{
 
147
        size_t goff;
 
148
        bitmap_t *gp;
 
149
        bitmap_t g;
 
150
        bool propagate;
 
151
 
 
152
        assert(bit < binfo->nbits);
 
153
        assert(bitmap_get(bitmap, binfo, bit));
 
154
        goff = bit >> LG_BITMAP_GROUP_NBITS;
 
155
        gp = &bitmap[goff];
 
156
        g = *gp;
 
157
        propagate = (g == 0);
 
158
        assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))) == 0);
 
159
        g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
 
160
        *gp = g;
 
161
        assert(bitmap_get(bitmap, binfo, bit) == false);
 
162
        /* Propagate group state transitions up the tree. */
 
163
        if (propagate) {
 
164
                unsigned i;
 
165
                for (i = 1; i < binfo->nlevels; i++) {
 
166
                        bit = goff;
 
167
                        goff = bit >> LG_BITMAP_GROUP_NBITS;
 
168
                        gp = &bitmap[binfo->levels[i].group_offset + goff];
 
169
                        g = *gp;
 
170
                        propagate = (g == 0);
 
171
                        assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)))
 
172
                            == 0);
 
173
                        g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
 
174
                        *gp = g;
 
175
                        if (propagate == false)
 
176
                                break;
 
177
                }
 
178
        }
 
179
}
 
180
 
 
181
#endif
 
182
 
 
183
#endif /* JEMALLOC_H_INLINES */
 
184
/******************************************************************************/