Signed-off-by: Thomas Jacob <jacob@xxxxxxxxxxxxx>
---
libiptc/libiptc.c | 199 +++++++++++++++++++++++++++++++++++++++++++++++++++--
1 files changed, 192 insertions(+), 7 deletions(-)
diff --git a/libiptc/libiptc.c b/libiptc/libiptc.c
index d0f51b4..e0c44c3 100644
--- a/libiptc/libiptc.c
+++ b/libiptc/libiptc.c
@@ -126,6 +126,26 @@ struct chain_head
unsigned int foot_offset; /* offset in rule blob */
};
+/* Max. number of chain_head per offsets chunk */
+#define OFFSETS_CHUNK_SIZE (1024)
+
+struct offsets_create_chunk
+{
+ struct list_head list;
+
+ unsigned int head_offset; /* of first entry */
+ unsigned int foot_offset; /* of last entry */
+
+ unsigned int num_entries; /* #entries */
+ struct chain_head * entries[OFFSETS_CHUNK_SIZE]; /* order by offset */
+};
+
+struct offsets_lookup_table
+{
+ unsigned int num_entries; /* #entries */
+ struct offsets_create_chunk ** entries; /* order by offset */
+};
+
STRUCT_TC_HANDLE
{
int changed; /* Have changes been made? */
@@ -140,6 +160,9 @@ STRUCT_TC_HANDLE
struct chain_head **chain_index; /* array for fast chain list access*/
unsigned int chain_index_sz;/* size of chain index array */
+ struct list_head offsets_create_list; /* array chunks created during data acquisition */
+ struct offsets_lookup_table offsets_search; /* final offsets search array */
+
STRUCT_GETINFO info;
STRUCT_GET_ENTRIES *entries;
};
@@ -568,6 +591,61 @@ static int iptcc_chain_index_delete_chain(struct chain_head *c, TC_HANDLE_T h)
/**********************************************************************
+ * iptc offsets index utility functions
+ **********************************************************************/
+
+/* Create offsets lookup table from the chunk list */
+static int iptcc_offsets_index_create(TC_HANDLE_T h)
+{
+ struct offsets_create_chunk * chunk;
+ unsigned int total_number=0;
+
+ /* First pass: count non-empty chunks and set their ranges */
+ list_for_each_entry(chunk, &h->offsets_create_list, list) {
+ if (chunk->num_entries>0) {
+ total_number++;
+ chunk->head_offset = chunk->entries[0]->head_offset;
+ chunk->foot_offset = chunk->entries[chunk->num_entries-1]->foot_offset;
+ }
+ }
+
+ /* No chains->nothing to assign */
+ if (total_number==0)
+ return 1;
+
+ h->offsets_search.entries = malloc(sizeof(struct offsets_create_chunk *)*total_number);
+ if (!h->offsets_search.entries)
+ return -ENOMEM;
+
+ /* Second pass: fill chunk table */
+ unsigned int i=0;
+ list_for_each_entry(chunk, &h->offsets_create_list, list)
+ if (chunk->num_entries>0)
+ h->offsets_search.entries[i++] = chunk;
+
+ h->offsets_search.num_entries = total_number;
+
+ return 1;
+}
+
+/* Free offsets lookup table AND the individual chunks */
+static void iptcc_offsets_index_free(TC_HANDLE_T h)
+{
+ struct offsets_create_chunk * chunk, *tmp;
+
+ if (h->offsets_search.num_entries>0) {
+ free(h->offsets_search.entries);
+ h->offsets_search.num_entries=0;
+ }
+
+ list_for_each_entry_safe(chunk, tmp, &h->offsets_create_list, list)
+ free(chunk);
+
+ INIT_LIST_HEAD(&h->offsets_create_list);
+}
+
+
+/**********************************************************************
* iptc cache utility functions (iptcc_*)
**********************************************************************/
@@ -625,6 +703,67 @@ iptcc_find_chain_by_offset(TC_HANDLE_T handle, unsigned int offset)
return NULL;
}
+
+/*
+ * Fast membership check on order arrays of inclusive intervals
+ * ( based on http://en.wikipedia.org/wiki/Binary_search )
+ *
+ * value: value to search for
+ * array: array of struct points
+ * left: struct attribute denoting left inclusive range limiter in array items
+ * right: struct attribute denoting left inclusive range limiter in array items
+ * size: number of items in array
+ * low, high, mid: temporary int variables
+ * result: index of range that contains value, or -1 if not found
+ */
+
+#define binary_array_range_search(value, array, left, right, size, low, high, mid, result) \
+ low = 0; \
+ high = size; \
+ result = -1; \
+ while(low<=high) \
+ { \
+ mid = (low + high) / 2; \
+ if ((array)[mid]->left > value) \
+ high = mid - 1; \
+ else if ((array)[mid]->right < value) \
+ low = mid + 1; \
+ else { \
+ if ((array)[mid]->left <= value && value <= (array)[mid]->right) \
+ result = mid; \
+ break; \
+ } \
+ }
+
+/* Returns chain head if found, otherwise NULL. */
+static struct chain_head *
+iptcc_find_chain_by_offset_fast(TC_HANDLE_T handle, unsigned int offset)
+{
+ int low,high,mid,result;
+
+ if (handle->offsets_search.num_entries==0)
+ return NULL;
+
+ /* find the chunk */
+ binary_array_range_search(offset, handle->offsets_search.entries, head_offset, foot_offset,
+ handle->offsets_search.num_entries, low, high, mid, result);
+
+ if (result<0)
+ return NULL;
+
+ /* find chain in chunk */
+ struct chain_head ** chunk_chains = handle->offsets_search.entries[result]->entries;
+ unsigned int num_entries = handle->offsets_search.entries[result]->num_entries;
+
+ binary_array_range_search(offset, chunk_chains, head_offset, foot_offset,
+ num_entries, low, high, mid, result);
+
+ if (result<0)
+ return NULL;
+
+ return chunk_chains[result];
+}
+
/* Returns chain head if found, otherwise NULL. */
static struct chain_head *
iptcc_find_label(const char *name, TC_HANDLE_T handle)
@@ -720,6 +859,19 @@ static void iptcc_delete_rule(struct rule_head *r)
* RULESET PARSER (blob -> cache)
**********************************************************************/
+/* Allocate another offsets chunk and append it to list */
+static int __iptcc_p_new_offsets_chunk(TC_HANDLE_T h)
+{
+ struct offsets_create_chunk * new_chunk = malloc(sizeof(struct offsets_create_chunk));
+
+ if (new_chunk) {
+ new_chunk->num_entries=0;
+ list_add_tail(&new_chunk->list, &h->offsets_create_list);
+ return 1;
+ }
+ return -1;
+}
+
/* Delete policy rule of previous chain, since cache doesn't contain
* chain policy rules.
* WARNING: This function has ugly design and relies on a lot of context, only
@@ -746,6 +898,19 @@ static int __iptcc_p_del_policy(TC_HANDLE_T h, unsigned int num)
h->chain_iterator_cur->foot_index = num;
h->chain_iterator_cur->foot_offset = pr->offset;
+ /* do we need a new offsets chunk? */
+ if (list_empty(&h->offsets_create_list) ||
+ list_entry(h->offsets_create_list.prev, struct offsets_create_chunk, list)->num_entries
+ >=OFFSETS_CHUNK_SIZE)
+ if (__iptcc_p_new_offsets_chunk(h)<0)
+ return -1;
+
+ /* add next chain to the current offsets chunk */
+ struct offsets_create_chunk * occ =
+ list_entry(h->offsets_create_list.prev, struct offsets_create_chunk, list);
+
+ occ->entries[occ->num_entries++]=h->chain_iterator_cur;
+
/* delete rule from cache */
iptcc_delete_rule(pr);
h->chain_iterator_cur->num_rules--;
@@ -799,13 +964,14 @@ static inline void iptc_insert_chain(TC_HANDLE_T h, struct chain_head *c)
/* Another ugly helper function split out of cache_add_entry to make it less
* spaghetti code */
-static void __iptcc_p_add_chain(TC_HANDLE_T h, struct chain_head *c,
+static int __iptcc_p_add_chain(TC_HANDLE_T h, struct chain_head *c,
unsigned int offset, unsigned int *num)
{
struct list_head *tail = h->chains.prev;
struct chain_head *ctail;
- __iptcc_p_del_policy(h, *num);
+ if ((__iptcc_p_del_policy(h, *num))<0)
+ return -1;
c->head_offset = offset;
c->index = *num;
@@ -826,6 +992,8 @@ static void __iptcc_p_add_chain(TC_HANDLE_T h, struct chain_head *c,
}
h->chain_iterator_cur = c;
+
+ return 1;
}
/* main parser function: add an entry from the blob to the cache */
@@ -844,7 +1012,10 @@ static int cache_add_entry(STRUCT_ENTRY *e,
/* This is the ERROR node at the end of the chain */
DEBUGP_C("%u:%u: end of table:\n", *num, offset);
- __iptcc_p_del_policy(h, *num);
+ if ((__iptcc_p_del_policy(h, *num))<0) {
+ errno = -ENOMEM;
+ return -1;
+ }
h->chain_iterator_cur = NULL;
goto out_inc;
@@ -864,8 +1035,10 @@ static int cache_add_entry(STRUCT_ENTRY *e,
}
h->num_chains++; /* New user defined chain */
- __iptcc_p_add_chain(h, c, offset, num);
-
+ if ((__iptcc_p_add_chain(h, c, offset, num))<0) {
+ errno = -ENOMEM;
+ return -1;
+ }
} else if ((builtin = iptcb_ent_is_hook_entry(e, h)) != 0) {
struct chain_head *c =
iptcc_alloc_chain_head((char *)hooknames[builtin-1],
@@ -879,7 +1052,10 @@ static int cache_add_entry(STRUCT_ENTRY *e,
c->hooknum = builtin;
- __iptcc_p_add_chain(h, c, offset, num);
+ if ((__iptcc_p_add_chain(h, c, offset, num))<0) {
+ errno = -ENOMEM;
+ return -1;
+ }
/* FIXME: this is ugly. */
goto new_rule;
@@ -955,6 +1131,10 @@ static int parse_table(TC_HANDLE_T h)
return -ENOMEM;
iptcc_chain_index_build(h);
+ /* Build the offsets lookup table */
+ if ((iptcc_offsets_index_create(h)) < 0)
+ return -ENOMEM;
+
/* Second pass: fixup parsed data from first pass */
list_for_each_entry(c, &h->chains, list) {
struct rule_head *r;
@@ -966,7 +1146,7 @@ static int parse_table(TC_HANDLE_T h)
continue;
t = (STRUCT_STANDARD_TARGET *)GET_TARGET(r->entry);
- lc = iptcc_find_chain_by_offset(h, t->verdict);
+ lc = iptcc_find_chain_by_offset_fast(h, t->verdict);
if (!lc)
return -1;
r->jump = lc;
@@ -974,6 +1154,9 @@ static int parse_table(TC_HANDLE_T h)
}
}
+ /* Don't need these tables anymore after beyond point */
+ iptcc_offsets_index_free(h);
+
/* FIXME: sort chains */
return 1;
@@ -1193,6 +1376,8 @@ alloc_handle(const char *tablename, unsigned int size, unsigned int num_rules)
strcpy(h->entries->name, tablename);
h->entries->size = size;
+ INIT_LIST_HEAD(&h->offsets_create_list);
+
return h;
out_free_handle:
--
1.5.4.3
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
