public inbox for lvm2-cvs@sourceware.org
help / color / mirror / Atom feed
* LVM2 ./WHATS_NEW_DM libdm/regex/matcher.c test ...
@ 2012-02-10 13:49 zkabelac
0 siblings, 0 replies; only message in thread
From: zkabelac @ 2012-02-10 13:49 UTC (permalink / raw)
To: lvm-devel, lvm2-cvs
CVSROOT: /cvs/lvm2
Module name: LVM2
Changes by: zkabelac@sourceware.org 2012-02-10 13:49:30
Modified files:
. : WHATS_NEW_DM
libdm/regex : matcher.c
test/unit : matcher_t.c
Log message:
Add test for memory allocation failures
Replace asserts with test for failing memory allocation.
Add at least stack traces.
Index counter starts from 1 (0 reserved for error), so replacing fingerprint.
Patches:
http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/WHATS_NEW_DM.diff?cvsroot=lvm2&r1=1.542&r2=1.543
http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/libdm/regex/matcher.c.diff?cvsroot=lvm2&r1=1.17&r2=1.18
http://sourceware.org/cgi-bin/cvsweb.cgi/LVM2/test/unit/matcher_t.c.diff?cvsroot=lvm2&r1=1.2&r2=1.3
--- LVM2/WHATS_NEW_DM 2012/02/08 12:59:19 1.542
+++ LVM2/WHATS_NEW_DM 2012/02/10 13:49:29 1.543
@@ -1,5 +1,6 @@
Version 1.02.70 -
===================================
+ Add test for memory allocation failures in regex matcher code.
Simplify dm_task_set_geometry() and use dm_asprintf().
Set all parameters to 0 for dm_get_next_target() for NULL return.
Fix fd resource leak in error path for _udev_notify_sem_create().
--- LVM2/libdm/regex/matcher.c 2011/04/08 14:40:21 1.17
+++ LVM2/libdm/regex/matcher.c 2012/02/10 13:49:30 1.18
@@ -1,6 +1,6 @@
/*
* Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.
- * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved.
+ * Copyright (C) 2004-2012 Red Hat, Inc. All rights reserved.
*
* This file is part of the device-mapper userspace tools.
*
@@ -98,16 +98,22 @@
m->charsets[m->charsets_entered++] = rx;
}
-static void _create_bitsets(struct dm_regex *m)
+static int _create_bitsets(struct dm_regex *m)
{
unsigned i;
+ struct rx_node *n;
for (i = 0; i < m->num_nodes; i++) {
- struct rx_node *n = m->nodes[i];
- n->firstpos = dm_bitset_create(m->scratch, m->num_charsets);
- n->lastpos = dm_bitset_create(m->scratch, m->num_charsets);
- n->followpos = dm_bitset_create(m->scratch, m->num_charsets);
+ n = m->nodes[i];
+ if (!(n->firstpos = dm_bitset_create(m->scratch, m->num_charsets)))
+ return_0;
+ if (!(n->lastpos = dm_bitset_create(m->scratch, m->num_charsets)))
+ return_0;
+ if (!(n->followpos = dm_bitset_create(m->scratch, m->num_charsets)))
+ return_0;
}
+
+ return 1;
}
static void _calc_functions(struct dm_regex *m)
@@ -206,14 +212,17 @@
struct dfa_state *dfa,
dm_bitset_t bits)
{
- dfa->bits = dm_bitset_create(mem, bits[0]); /* first element is the size */
+ if (!(dfa->bits = dm_bitset_create(mem, bits[0]))) /* first element is the size */
+ return_NULL;
+
dm_bit_copy(dfa->bits, bits);
dfa->next = 0;
- dfa->final = -1;
+ dfa->final = -1;
+
return dfa;
}
-static void _calc_state(struct dm_regex *m, struct dfa_state *dfa, int a)
+static int _calc_state(struct dm_regex *m, struct dfa_state *dfa, int a)
{
int set_bits = 0, i;
dm_bitset_t dfa_bits = dfa->bits;
@@ -233,9 +242,12 @@
struct dfa_state *ldfa = ttree_lookup(m->tt, m->bs + 1);
if (!ldfa) {
/* push */
- ldfa = _create_dfa_state(m->mem);
- ttree_insert(m->tt, m->bs + 1, ldfa);
- tmp = _create_state_queue(m->scratch, ldfa, m->bs);
+ if (!(ldfa = _create_dfa_state(m->mem)))
+ return_0;
+
+ ttree_insert(m->tt, m->bs + 1, ldfa);
+ if (!(tmp = _create_state_queue(m->scratch, ldfa, m->bs)))
+ return_0;
if (!m->h)
m->h = m->t = tmp;
else {
@@ -247,32 +259,32 @@
dfa->lookup[a] = ldfa;
dm_bit_clear_all(m->bs);
}
+
+ return 1;
}
static int _calc_states(struct dm_regex *m, struct rx_node *rx)
{
unsigned iwidth = (m->num_charsets / DM_BITS_PER_INT) + 1;
struct dfa_state *dfa;
+ struct rx_node *n;
unsigned i;
int a;
- m->tt = ttree_create(m->scratch, iwidth);
- if (!m->tt)
+ if (!(m->tt = ttree_create(m->scratch, iwidth)))
return_0;
if (!(m->bs = dm_bitset_create(m->scratch, m->num_charsets)))
return_0;
/* build some char maps */
- for (a = 0; a < 256; a++) {
- m->charmap[a] = dm_bitset_create(m->scratch, m->num_charsets);
- if (!m->charmap[a])
- return_0;
- }
+ for (a = 0; a < 256; a++)
+ if (!(m->charmap[a] = dm_bitset_create(m->scratch, m->num_charsets)))
+ return_0;
for (i = 0; i < m->num_nodes; i++) {
- struct rx_node *n = m->nodes[i];
- if (n->type == CHARSET) {
+ n = m->nodes[i];
+ if (n->type == CHARSET) {
for (a = dm_bit_get_first(n->charset);
a >= 0; a = dm_bit_get_next(n->charset, a))
dm_bit_set(m->charmap[a], n->charset_index);
@@ -280,13 +292,19 @@
}
/* create first state */
- dfa = _create_dfa_state(m->mem);
+ if (!(dfa = _create_dfa_state(m->mem)))
+ return_0;
+
m->start = dfa;
ttree_insert(m->tt, rx->firstpos + 1, dfa);
/* prime the queue */
- m->h = m->t = _create_state_queue(m->scratch, dfa, rx->firstpos);
- m->dfa_copy = dm_bitset_create(m->scratch, m->num_charsets);
+ if (!(m->h = m->t = _create_state_queue(m->scratch, dfa, rx->firstpos)))
+ return_0;
+
+ if (!(m->dfa_copy = dm_bitset_create(m->scratch, m->num_charsets)))
+ return_0;
+
return 1;
}
@@ -294,7 +312,7 @@
* Forces all the dfa states to be calculated up front, ie. what
* _calc_states() used to do before we switched to calculating on demand.
*/
-static void _force_states(struct dm_regex *m)
+static int _force_states(struct dm_regex *m)
{
int a;
@@ -307,8 +325,11 @@
/* iterate through all the inputs for this state */
dm_bit_clear_all(m->bs);
for (a = 0; a < 256; a++)
- _calc_state(m, s, a);
+ if (!_calc_state(m, s, a))
+ return_0;
}
+
+ return 1;
}
struct dm_regex *dm_regex_create(struct dm_pool *mem, const char * const *patterns,
@@ -348,24 +369,29 @@
m->mem = mem;
m->scratch = scratch;
m->num_nodes = _count_nodes(rx);
- m->num_charsets = _count_charsets(rx);
- _enumerate_charsets(rx);
- m->nodes = dm_pool_alloc(scratch, sizeof(*m->nodes) * m->num_nodes);
- if (!m->nodes)
+ m->num_charsets = _count_charsets(rx);
+ _enumerate_charsets(rx);
+ if (!(m->nodes = dm_pool_alloc(scratch, sizeof(*m->nodes) * m->num_nodes)))
goto_bad;
- m->charsets = dm_pool_alloc(scratch, sizeof(*m->charsets) * m->num_charsets);
- if (!m->charsets)
- goto_bad;
+ if (!(m->charsets = dm_pool_alloc(scratch, sizeof(*m->charsets) * m->num_charsets)))
+ goto_bad;
_fill_table(m, rx);
- _create_bitsets(m);
+
+ if (!_create_bitsets(m))
+ goto_bad;
+
_calc_functions(m);
- _calc_states(m, rx);
+
+ if (!_calc_states(m, rx))
+ goto_bad;
+
return m;
bad:
dm_pool_free(mem, m);
+
return NULL;
}
@@ -374,14 +400,17 @@
struct dfa_state *ns;
if (!(ns = cs->lookup[(unsigned char) c])) {
- _calc_state(m, cs, (unsigned char) c);
+ if (!_calc_state(m, cs, (unsigned char) c))
+ return_NULL;
+
if (!(ns = cs->lookup[(unsigned char) c]))
return NULL;
}
// yuck, we have to special case the target trans
- if (ns->final == -1)
- _calc_state(m, ns, TARGET_TRANS);
+ if ((ns->final == -1) &&
+ !_calc_state(m, ns, TARGET_TRANS))
+ return_NULL;
if (ns->final && (ns->final > *r))
*r = ns->final;
@@ -434,14 +463,14 @@
unsigned next_index;
};
-static uint32_t randomise_(uint32_t n)
+static uint32_t _randomise(uint32_t n)
{
/* 2^32 - 5 */
uint32_t const prime = (~0) - 4;
return n * prime;
}
-static int seen_(struct node_list *n, struct dfa_state *node, uint32_t *i)
+static int _seen(struct node_list *n, struct dfa_state *node, uint32_t *i)
{
while (n) {
if (n->node == node) {
@@ -457,32 +486,36 @@
/*
* Push node if it's not been seen before, returning a unique index.
*/
-static uint32_t push_node_(struct printer *p, struct dfa_state *node)
+static uint32_t _push_node(struct printer *p, struct dfa_state *node)
{
uint32_t i;
- if (seen_(p->pending, node, &i) ||
- seen_(p->processed, node, &i))
+ struct node_list *n;
+
+ if (_seen(p->pending, node, &i) ||
+ _seen(p->processed, node, &i))
return i;
- else {
- struct node_list *n = dm_pool_alloc(p->mem, sizeof(*n));
- assert(n);
- n->node_id = p->next_index++;
- n->node = node;
- n->next = p->pending;
- p->pending = n;
- return n->node_id;
- }
+
+ if (!(n = dm_pool_alloc(p->mem, sizeof(*n))))
+ return_0;
+
+ n->node_id = ++p->next_index; /* start from 1, keep 0 as error code */
+ n->node = node;
+ n->next = p->pending;
+ p->pending = n;
+
+ return n->node_id;
}
/*
* Pop the front node, and fill out it's previously assigned index.
*/
-static struct dfa_state *pop_node_(struct printer *p)
+static struct dfa_state *_pop_node(struct printer *p)
{
struct dfa_state *node = NULL;
+ struct node_list *n;
- if (p->pending) {
- struct node_list *n = p->pending;
+ if (p->pending) {
+ n = p->pending;
p->pending = n->next;
n->next = p->processed;
p->processed = n;
@@ -493,22 +526,22 @@
return node;
}
-static uint32_t combine_(uint32_t n1, uint32_t n2)
+static uint32_t _combine(uint32_t n1, uint32_t n2)
{
- return ((n1 << 8) | (n1 >> 24)) ^ randomise_(n2);
+ return ((n1 << 8) | (n1 >> 24)) ^ _randomise(n2);
}
-static uint32_t fingerprint_(struct printer *p)
+static uint32_t _fingerprint(struct printer *p)
{
int c;
uint32_t result = 0;
struct dfa_state *node;
- while ((node = pop_node_(p))) {
- result = combine_(result, node->final < 0 ? 0 : node->final);
+ while ((node = _pop_node(p))) {
+ result = _combine(result, (node->final < 0) ? 0 : node->final);
for (c = 0; c < 256; c++)
- result = combine_(result,
- push_node_(p, node->lookup[c]));
+ result = _combine(result,
+ _push_node(p, node->lookup[c]));
}
return result;
@@ -516,20 +549,27 @@
uint32_t dm_regex_fingerprint(struct dm_regex *regex)
{
- uint32_t result;
struct printer p;
+ uint32_t result = 0;
struct dm_pool *mem = dm_pool_create("regex fingerprint", 1024);
- _force_states(regex);
+ if (!mem)
+ return_0;
+
+ if (!_force_states(regex))
+ goto_out;
- assert(mem);
p.mem = mem;
p.pending = NULL;
p.processed = NULL;
p.next_index = 0;
- push_node_(&p, regex->start);
- result = fingerprint_(&p);
+ if (!_push_node(&p, regex->start))
+ goto_out;
+
+ result = _fingerprint(&p);
+out:
dm_pool_destroy(mem);
+
return result;
}
--- LVM2/test/unit/matcher_t.c 2011/12/13 12:08:42 1.2
+++ LVM2/test/unit/matcher_t.c 2012/02/10 13:49:30 1.3
@@ -58,10 +58,10 @@
struct dm_regex *scanner;
scanner = make_scanner(dev_patterns);
- CU_ASSERT_EQUAL(dm_regex_fingerprint(scanner), 0x352b6c4f);
+ CU_ASSERT_EQUAL(dm_regex_fingerprint(scanner), 0x7f556c09);
scanner = make_scanner(random_patterns);
- CU_ASSERT_EQUAL(dm_regex_fingerprint(scanner), 0xeed8ceb8);
+ CU_ASSERT_EQUAL(dm_regex_fingerprint(scanner), 0x9f11076c);
}
static void test_matching(void) {
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2012-02-10 13:49 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-02-10 13:49 LVM2 ./WHATS_NEW_DM libdm/regex/matcher.c test zkabelac
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).