| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Tue, 22 Apr 2014 18:16:20 +0800
From: Lai Jiangshan <laijs@...fujitsu.com>
To: <linux-kernel@...r.kernel.org>
CC: Andrew Morton <akpm@...ux-foundation.org>,
Tejun Heo <tj@...nel.org>,
Lai Jiangshan <laijs@...fujitsu.com>,
Vladimir Davydov <vdavydov@...allels.com>,
Jiri Kosina <jkosina@...e.cz>,
Jeff Layton <jlayton@...hat.com>,
Andreas Gruenbacher <agruen@...bit.com>,
Stephen Hemminger <stephen@...workplumber.org>,
Jean Delvare <jdelvare@...e.de>,
Monam Agarwal <monamagarwal123@...il.com>
Subject: [PATCH 3/4] ida: in-place ida allocation
There are two stages of ida allocation/free, idr_layers and ida_bitmap.
They add unneeded foot print and memory waste.
When a single ID is first allocated from an ida, this ida requires
two big chunks of memory. One idr_layer and one ida_bitmap.
To reduce the foot print and memory, we reduce the ida_bitmap
to a single "unsigned long" and place it in its own idr-slot
and avoid to allocate the ida_bitmap.
It also means ida bitmap is located on its coresponding idr-slot
which size is the same as "unsigned long".
Each ida bitmap(idr-slot) contains BITS_PER_LONG ida-slots.
The struct ida_bitmap is not needed any more, we use "unsigned long"
directly and remove all the code of alloc/free struct ida_bitmap.
Signed-off-by: Lai Jiangshan <laijs@...fujitsu.com>
---
include/linux/idr.h | 15 +--------
lib/idr.c | 85 +++++++++++++-------------------------------------
2 files changed, 23 insertions(+), 77 deletions(-)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index 6af3400..3a77b33 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -135,25 +135,12 @@ static inline void *idr_find(struct idr *idr, int id)
/*
* IDA - IDR based id allocator, use when translation from id to
* pointer isn't necessary.
- *
- * IDA_BITMAP_LONGS is calculated to be one less to accommodate
- * ida_bitmap->nr_busy so that the whole struct fits in 128 bytes.
*/
-#define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */
-#define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long) - 1)
-#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8)
-
-struct ida_bitmap {
- long nr_busy;
- unsigned long bitmap[IDA_BITMAP_LONGS];
-};
-
struct ida {
struct idr idr;
- struct ida_bitmap *free_bitmap;
};
-#define IDA_INIT(name) { .idr = IDR_INIT((name).idr), .free_bitmap = NULL, }
+#define IDA_INIT(name) { .idr = IDR_INIT((name).idr), }
#define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
int ida_pre_get(struct ida *ida, gfp_t gfp_mask);
diff --git a/lib/idr.c b/lib/idr.c
index 871991b..69f8d78 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -859,27 +859,15 @@ EXPORT_SYMBOL(idr_is_empty);
*
* This is id allocator without id -> pointer translation. Memory
* usage is much lower than full blown idr because each id only
- * occupies a bit. ida uses a custom leaf node which contains
- * IDA_BITMAP_BITS slots.
+ * occupies a bit. ida uses the leaf idr-slot which contains
+ * IDA_BITMAP_BITS(BITS_PER_LONG) ida-slots.
*
* 2007-04-25 written by Tejun Heo <htejun@...il.com>
*/
-static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap)
-{
- unsigned long flags;
-
- if (!ida->free_bitmap) {
- spin_lock_irqsave(&ida->idr.lock, flags);
- if (!ida->free_bitmap) {
- ida->free_bitmap = bitmap;
- bitmap = NULL;
- }
- spin_unlock_irqrestore(&ida->idr.lock, flags);
- }
-
- kfree(bitmap);
-}
+#define IDA_BITMAP_BITS BITS_PER_LONG
+#define IDA_BITMAP_EMPTY 0UL
+#define IDA_BITMAP_FULL (~0UL)
/**
* ida_pre_get - reserve resources for ida allocation
@@ -896,21 +884,7 @@ static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap)
int ida_pre_get(struct ida *ida, gfp_t gfp_mask)
{
/* allocate idr_layers */
- if (!__idr_pre_get(&ida->idr, gfp_mask))
- return 0;
-
- /* allocate free_bitmap */
- if (!ida->free_bitmap) {
- struct ida_bitmap *bitmap;
-
- bitmap = kmalloc(sizeof(struct ida_bitmap), gfp_mask);
- if (!bitmap)
- return 0;
-
- free_bitmap(ida, bitmap);
- }
-
- return 1;
+ return __idr_pre_get(&ida->idr, gfp_mask);
}
EXPORT_SYMBOL(ida_pre_get);
@@ -932,8 +906,7 @@ EXPORT_SYMBOL(ida_pre_get);
int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
{
struct idr_layer *pa[MAX_IDR_LEVEL + 1];
- struct ida_bitmap *bitmap;
- unsigned long flags;
+ unsigned long *bitmap;
int idr_id = starting_id / IDA_BITMAP_BITS;
int offset = starting_id % IDA_BITMAP_BITS;
int t, id;
@@ -951,25 +924,11 @@ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
offset = 0;
idr_id = t;
- /* if bitmap isn't there, create a new one */
- bitmap = (void *)pa[0]->ary[idr_id & IDR_MASK];
- if (!bitmap) {
- spin_lock_irqsave(&ida->idr.lock, flags);
- bitmap = ida->free_bitmap;
- ida->free_bitmap = NULL;
- spin_unlock_irqrestore(&ida->idr.lock, flags);
-
- if (!bitmap)
- return -EAGAIN;
-
- memset(bitmap, 0, sizeof(struct ida_bitmap));
- rcu_assign_pointer(pa[0]->ary[idr_id & IDR_MASK],
- (void *)bitmap);
- pa[0]->count++;
- }
+ /* the lelf idr-slot is the bitmap for ida slots */
+ bitmap = (void *)&pa[0]->ary[idr_id & IDR_MASK];
/* lookup for empty slot */
- t = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, offset);
+ t = find_next_zero_bit(bitmap, IDA_BITMAP_BITS, offset);
if (t == IDA_BITMAP_BITS) {
/* no empty slot after offset, continue to the next chunk */
idr_id++;
@@ -981,18 +940,21 @@ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
if (id >= MAX_IDR_BIT)
return -ENOSPC;
- __set_bit(t, bitmap->bitmap);
- if (++bitmap->nr_busy == IDA_BITMAP_BITS)
+ if (*bitmap == IDA_BITMAP_EMPTY)
+ pa[0]->count++;
+
+ __set_bit(t, bitmap);
+ if (*bitmap == IDA_BITMAP_FULL)
idr_mark_full(pa, idr_id);
*p_id = id;
- /* Each leaf node can handle nearly a thousand slots and the
+ /* Each leaf idr_layer can handle nearly a thousand slots and the
* whole idea of ida is to have small memory foot print.
* Throw away extra resources one by one after each successful
* allocation.
*/
- if (ida->idr.id_free_cnt || ida->free_bitmap) {
+ if (ida->idr.id_free_cnt) {
struct idr_layer *p = get_from_free_list(&ida->idr);
if (p)
kmem_cache_free(idr_layer_cache, p);
@@ -1014,7 +976,7 @@ void ida_remove(struct ida *ida, int id)
int idr_id = id / IDA_BITMAP_BITS;
int offset = id % IDA_BITMAP_BITS;
int n;
- struct ida_bitmap *bitmap;
+ unsigned long *bitmap;
if (id < 0 || idr_id > idr_max(ida->idr.layers))
goto err;
@@ -1033,16 +995,15 @@ void ida_remove(struct ida *ida, int id)
n = idr_id & IDR_MASK;
__clear_bit(n, p->bitmap);
- bitmap = (void *)p->ary[n];
- if (!bitmap || !test_bit(offset, bitmap->bitmap))
+ bitmap = (void *)&p->ary[n];
+ if (!test_bit(offset, bitmap))
goto err;
/* update bitmap and remove it if empty */
- __clear_bit(offset, bitmap->bitmap);
- if (--bitmap->nr_busy == 0) {
+ __clear_bit(offset, bitmap);
+ if (*bitmap == IDA_BITMAP_EMPTY) {
__set_bit(n, p->bitmap); /* to please idr_remove() */
idr_remove(&ida->idr, idr_id);
- free_bitmap(ida, bitmap);
}
return;
@@ -1059,7 +1020,6 @@ EXPORT_SYMBOL(ida_remove);
void ida_destroy(struct ida *ida)
{
idr_destroy(&ida->idr);
- kfree(ida->free_bitmap);
}
EXPORT_SYMBOL(ida_destroy);
@@ -1142,7 +1102,6 @@ EXPORT_SYMBOL(ida_simple_remove);
*/
void ida_init(struct ida *ida)
{
- memset(ida, 0, sizeof(struct ida));
idr_init(&ida->idr);
}
--
1.7.4.4
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists