* [PATCH 1/7] openvswitch: convert to kvmalloc
2018-12-17 13:19 [PATCH 0/7] generic radix trees; drop flex arrays Kent Overstreet
@ 2018-12-17 13:19 ` Kent Overstreet
2018-12-17 13:19 ` [PATCH 2/7] md: " Kent Overstreet
` (5 subsequent siblings)
6 siblings, 0 replies; 15+ messages in thread
From: Kent Overstreet @ 2018-12-17 13:19 UTC (permalink / raw)
To: akpm, linux-kernel; +Cc: Kent Overstreet, Pravin B Shelar, dev, Matthew Wilcox
There was no real need for this code to be using flexarrays, it's just
implementing a hash table - ideally it would be using rhashtables, but
that conversion would be significantly more complicated.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Cc: Pravin B Shelar <pshelar@ovn.org>
Cc: dev@openvswitch.org
Reviewed-by: Matthew Wilcox <willy@infradead.org>
---
net/openvswitch/flow.h | 1 -
net/openvswitch/flow_netlink.h | 1 -
net/openvswitch/flow_table.c | 51 ++++++++--------------------------
net/openvswitch/flow_table.h | 3 +-
4 files changed, 13 insertions(+), 43 deletions(-)
diff --git a/net/openvswitch/flow.h b/net/openvswitch/flow.h
index c670dd24b8..4f06278166 100644
--- a/net/openvswitch/flow.h
+++ b/net/openvswitch/flow.h
@@ -30,7 +30,6 @@
#include <linux/in6.h>
#include <linux/jiffies.h>
#include <linux/time.h>
-#include <linux/flex_array.h>
#include <linux/cpumask.h>
#include <net/inet_ecn.h>
#include <net/ip_tunnels.h>
diff --git a/net/openvswitch/flow_netlink.h b/net/openvswitch/flow_netlink.h
index 6657606b2b..66f9553758 100644
--- a/net/openvswitch/flow_netlink.h
+++ b/net/openvswitch/flow_netlink.h
@@ -30,7 +30,6 @@
#include <linux/in6.h>
#include <linux/jiffies.h>
#include <linux/time.h>
-#include <linux/flex_array.h>
#include <net/inet_ecn.h>
#include <net/ip_tunnels.h>
diff --git a/net/openvswitch/flow_table.c b/net/openvswitch/flow_table.c
index 80ea2a7185..cfb0098c9a 100644
--- a/net/openvswitch/flow_table.c
+++ b/net/openvswitch/flow_table.c
@@ -111,29 +111,6 @@ int ovs_flow_tbl_count(const struct flow_table *table)
return table->count;
}
-static struct flex_array *alloc_buckets(unsigned int n_buckets)
-{
- struct flex_array *buckets;
- int i, err;
-
- buckets = flex_array_alloc(sizeof(struct hlist_head),
- n_buckets, GFP_KERNEL);
- if (!buckets)
- return NULL;
-
- err = flex_array_prealloc(buckets, 0, n_buckets, GFP_KERNEL);
- if (err) {
- flex_array_free(buckets);
- return NULL;
- }
-
- for (i = 0; i < n_buckets; i++)
- INIT_HLIST_HEAD((struct hlist_head *)
- flex_array_get(buckets, i));
-
- return buckets;
-}
-
static void flow_free(struct sw_flow *flow)
{
int cpu;
@@ -168,31 +145,30 @@ void ovs_flow_free(struct sw_flow *flow, bool deferred)
flow_free(flow);
}
-static void free_buckets(struct flex_array *buckets)
-{
- flex_array_free(buckets);
-}
-
-
static void __table_instance_destroy(struct table_instance *ti)
{
- free_buckets(ti->buckets);
+ kvfree(ti->buckets);
kfree(ti);
}
static struct table_instance *table_instance_alloc(int new_size)
{
struct table_instance *ti = kmalloc(sizeof(*ti), GFP_KERNEL);
+ int i;
if (!ti)
return NULL;
- ti->buckets = alloc_buckets(new_size);
-
+ ti->buckets = kvmalloc_array(new_size, sizeof(struct hlist_head),
+ GFP_KERNEL);
if (!ti->buckets) {
kfree(ti);
return NULL;
}
+
+ for (i = 0; i < new_size; i++)
+ INIT_HLIST_HEAD(&ti->buckets[i]);
+
ti->n_buckets = new_size;
ti->node_ver = 0;
ti->keep_flows = false;
@@ -249,7 +225,7 @@ static void table_instance_destroy(struct table_instance *ti,
for (i = 0; i < ti->n_buckets; i++) {
struct sw_flow *flow;
- struct hlist_head *head = flex_array_get(ti->buckets, i);
+ struct hlist_head *head = &ti->buckets[i];
struct hlist_node *n;
int ver = ti->node_ver;
int ufid_ver = ufid_ti->node_ver;
@@ -294,7 +270,7 @@ struct sw_flow *ovs_flow_tbl_dump_next(struct table_instance *ti,
ver = ti->node_ver;
while (*bucket < ti->n_buckets) {
i = 0;
- head = flex_array_get(ti->buckets, *bucket);
+ head = &ti->buckets[*bucket];
hlist_for_each_entry_rcu(flow, head, flow_table.node[ver]) {
if (i < *last) {
i++;
@@ -313,8 +289,7 @@ struct sw_flow *ovs_flow_tbl_dump_next(struct table_instance *ti,
static struct hlist_head *find_bucket(struct table_instance *ti, u32 hash)
{
hash = jhash_1word(hash, ti->hash_seed);
- return flex_array_get(ti->buckets,
- (hash & (ti->n_buckets - 1)));
+ return &ti->buckets[hash & (ti->n_buckets - 1)];
}
static void table_instance_insert(struct table_instance *ti,
@@ -347,9 +322,7 @@ static void flow_table_copy_flows(struct table_instance *old,
/* Insert in new table. */
for (i = 0; i < old->n_buckets; i++) {
struct sw_flow *flow;
- struct hlist_head *head;
-
- head = flex_array_get(old->buckets, i);
+ struct hlist_head *head = &old->buckets[i];
if (ufid)
hlist_for_each_entry(flow, head,
diff --git a/net/openvswitch/flow_table.h b/net/openvswitch/flow_table.h
index 2dd9900f53..de5ec6cf51 100644
--- a/net/openvswitch/flow_table.h
+++ b/net/openvswitch/flow_table.h
@@ -29,7 +29,6 @@
#include <linux/in6.h>
#include <linux/jiffies.h>
#include <linux/time.h>
-#include <linux/flex_array.h>
#include <net/inet_ecn.h>
#include <net/ip_tunnels.h>
@@ -37,7 +36,7 @@
#include "flow.h"
struct table_instance {
- struct flex_array *buckets;
+ struct hlist_head *buckets;
unsigned int n_buckets;
struct rcu_head rcu;
int node_ver;
--
2.20.1
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 2/7] md: convert to kvmalloc
2018-12-17 13:19 [PATCH 0/7] generic radix trees; drop flex arrays Kent Overstreet
2018-12-17 13:19 ` [PATCH 1/7] openvswitch: convert to kvmalloc Kent Overstreet
@ 2018-12-17 13:19 ` Kent Overstreet
2018-12-17 13:19 ` [PATCH 3/7] selinux: " Kent Overstreet
` (4 subsequent siblings)
6 siblings, 0 replies; 15+ messages in thread
From: Kent Overstreet @ 2018-12-17 13:19 UTC (permalink / raw)
To: akpm, linux-kernel
Cc: Kent Overstreet, Shaohua Li, linux-raid, Matthew Wilcox
The code really just wants a big flat buffer, so just do that.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Cc: Shaohua Li <shli@kernel.org>
Cc: linux-raid@vger.kernel.org
Reviewed-by: Matthew Wilcox <willy@infradead.org>
---
drivers/md/raid5-ppl.c | 6 +--
drivers/md/raid5.c | 87 +++++++++++++++++++-----------------------
drivers/md/raid5.h | 9 +++--
3 files changed, 46 insertions(+), 56 deletions(-)
diff --git a/drivers/md/raid5-ppl.c b/drivers/md/raid5-ppl.c
index 3a7c363265..0b096ddc9c 100644
--- a/drivers/md/raid5-ppl.c
+++ b/drivers/md/raid5-ppl.c
@@ -16,7 +16,6 @@
#include <linux/blkdev.h>
#include <linux/slab.h>
#include <linux/crc32c.h>
-#include <linux/flex_array.h>
#include <linux/async_tx.h>
#include <linux/raid/md_p.h>
#include "md.h"
@@ -165,7 +164,7 @@ ops_run_partial_parity(struct stripe_head *sh, struct raid5_percpu *percpu,
struct dma_async_tx_descriptor *tx)
{
int disks = sh->disks;
- struct page **srcs = flex_array_get(percpu->scribble, 0);
+ struct page **srcs = percpu->scribble;
int count = 0, pd_idx = sh->pd_idx, i;
struct async_submit_ctl submit;
@@ -196,8 +195,7 @@ ops_run_partial_parity(struct stripe_head *sh, struct raid5_percpu *percpu,
}
init_async_submit(&submit, ASYNC_TX_FENCE|ASYNC_TX_XOR_ZERO_DST, tx,
- NULL, sh, flex_array_get(percpu->scribble, 0)
- + sizeof(struct page *) * (sh->disks + 2));
+ NULL, sh, (void *) (srcs + sh->disks + 2));
if (count == 1)
tx = async_memcpy(sh->ppl_page, srcs[0], 0, 0, PAGE_SIZE,
diff --git a/drivers/md/raid5.c b/drivers/md/raid5.c
index 4990f0319f..c92e26fbcd 100644
--- a/drivers/md/raid5.c
+++ b/drivers/md/raid5.c
@@ -54,7 +54,6 @@
#include <linux/slab.h>
#include <linux/ratelimit.h>
#include <linux/nodemask.h>
-#include <linux/flex_array.h>
#include <trace/events/block.h>
#include <linux/list_sort.h>
@@ -1394,22 +1393,16 @@ static void ops_complete_compute(void *stripe_head_ref)
}
/* return a pointer to the address conversion region of the scribble buffer */
-static addr_conv_t *to_addr_conv(struct stripe_head *sh,
- struct raid5_percpu *percpu, int i)
+static struct page **to_addr_page(struct raid5_percpu *percpu, int i)
{
- void *addr;
-
- addr = flex_array_get(percpu->scribble, i);
- return addr + sizeof(struct page *) * (sh->disks + 2);
+ return percpu->scribble + i * percpu->scribble_obj_size;
}
/* return a pointer to the address conversion region of the scribble buffer */
-static struct page **to_addr_page(struct raid5_percpu *percpu, int i)
+static addr_conv_t *to_addr_conv(struct stripe_head *sh,
+ struct raid5_percpu *percpu, int i)
{
- void *addr;
-
- addr = flex_array_get(percpu->scribble, i);
- return addr;
+ return (void *) (to_addr_page(percpu, i) + sh->disks + 2);
}
static struct dma_async_tx_descriptor *
@@ -2238,21 +2231,23 @@ static int grow_stripes(struct r5conf *conf, int num)
* calculate over all devices (not just the data blocks), using zeros in place
* of the P and Q blocks.
*/
-static struct flex_array *scribble_alloc(int num, int cnt, gfp_t flags)
+static int scribble_alloc(struct raid5_percpu *percpu,
+ int num, int cnt, gfp_t flags)
{
- struct flex_array *ret;
- size_t len;
+ size_t obj_size =
+ sizeof(struct page *) * (num+2) +
+ sizeof(addr_conv_t) * (num+2);
+ void *scribble;
- len = sizeof(struct page *) * (num+2) + sizeof(addr_conv_t) * (num+2);
- ret = flex_array_alloc(len, cnt, flags);
- if (!ret)
- return NULL;
- /* always prealloc all elements, so no locking is required */
- if (flex_array_prealloc(ret, 0, cnt, flags)) {
- flex_array_free(ret);
- return NULL;
- }
- return ret;
+ scribble = kvmalloc_array(cnt, obj_size, flags);
+ if (!scribble)
+ return -ENOMEM;
+
+ kvfree(percpu->scribble);
+
+ percpu->scribble = scribble;
+ percpu->scribble_obj_size = obj_size;
+ return 0;
}
static int resize_chunks(struct r5conf *conf, int new_disks, int new_sectors)
@@ -2270,23 +2265,18 @@ static int resize_chunks(struct r5conf *conf, int new_disks, int new_sectors)
return 0;
mddev_suspend(conf->mddev);
get_online_cpus();
+
for_each_present_cpu(cpu) {
struct raid5_percpu *percpu;
- struct flex_array *scribble;
percpu = per_cpu_ptr(conf->percpu, cpu);
- scribble = scribble_alloc(new_disks,
- new_sectors / STRIPE_SECTORS,
- GFP_NOIO);
-
- if (scribble) {
- flex_array_free(percpu->scribble);
- percpu->scribble = scribble;
- } else {
- err = -ENOMEM;
+ err = scribble_alloc(percpu, new_disks,
+ new_sectors / STRIPE_SECTORS,
+ GFP_NOIO);
+ if (err)
break;
- }
}
+
put_online_cpus();
mddev_resume(conf->mddev);
if (!err) {
@@ -6738,25 +6728,26 @@ raid5_size(struct mddev *mddev, sector_t sectors, int raid_disks)
static void free_scratch_buffer(struct r5conf *conf, struct raid5_percpu *percpu)
{
safe_put_page(percpu->spare_page);
- if (percpu->scribble)
- flex_array_free(percpu->scribble);
percpu->spare_page = NULL;
+ kvfree(percpu->scribble);
percpu->scribble = NULL;
}
static int alloc_scratch_buffer(struct r5conf *conf, struct raid5_percpu *percpu)
{
- if (conf->level == 6 && !percpu->spare_page)
+ if (conf->level == 6 && !percpu->spare_page) {
percpu->spare_page = alloc_page(GFP_KERNEL);
- if (!percpu->scribble)
- percpu->scribble = scribble_alloc(max(conf->raid_disks,
- conf->previous_raid_disks),
- max(conf->chunk_sectors,
- conf->prev_chunk_sectors)
- / STRIPE_SECTORS,
- GFP_KERNEL);
-
- if (!percpu->scribble || (conf->level == 6 && !percpu->spare_page)) {
+ if (!percpu->spare_page)
+ return -ENOMEM;
+ }
+
+ if (scribble_alloc(percpu,
+ max(conf->raid_disks,
+ conf->previous_raid_disks),
+ max(conf->chunk_sectors,
+ conf->prev_chunk_sectors)
+ / STRIPE_SECTORS,
+ GFP_KERNEL)) {
free_scratch_buffer(conf, percpu);
return -ENOMEM;
}
diff --git a/drivers/md/raid5.h b/drivers/md/raid5.h
index 8474c22412..cf991f1340 100644
--- a/drivers/md/raid5.h
+++ b/drivers/md/raid5.h
@@ -638,10 +638,11 @@ struct r5conf {
/* per cpu variables */
struct raid5_percpu {
struct page *spare_page; /* Used when checking P/Q in raid6 */
- struct flex_array *scribble; /* space for constructing buffer
- * lists and performing address
- * conversions
- */
+ void *scribble; /* space for constructing buffer
+ * lists and performing address
+ * conversions
+ */
+ int scribble_obj_size;
} __percpu *percpu;
int scribble_disks;
int scribble_sectors;
--
2.20.1
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 3/7] selinux: convert to kvmalloc
2018-12-17 13:19 [PATCH 0/7] generic radix trees; drop flex arrays Kent Overstreet
2018-12-17 13:19 ` [PATCH 1/7] openvswitch: convert to kvmalloc Kent Overstreet
2018-12-17 13:19 ` [PATCH 2/7] md: " Kent Overstreet
@ 2018-12-17 13:19 ` Kent Overstreet
2018-12-17 13:19 ` [PATCH 4/7] Generic radix trees Kent Overstreet
` (3 subsequent siblings)
6 siblings, 0 replies; 15+ messages in thread
From: Kent Overstreet @ 2018-12-17 13:19 UTC (permalink / raw)
To: akpm, linux-kernel; +Cc: Kent Overstreet, linux-security-module
The flex arrays were being used for constant sized arrays, so there's no
benefit to using flex_arrays over something simpler.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Cc: linux-security-module@vger.kernel.org
---
security/selinux/ss/avtab.c | 40 +++++-----
security/selinux/ss/avtab.h | 4 +-
security/selinux/ss/conditional.c | 6 +-
security/selinux/ss/policydb.c | 122 ++++++++----------------------
security/selinux/ss/policydb.h | 12 +--
security/selinux/ss/services.c | 22 ++----
6 files changed, 62 insertions(+), 144 deletions(-)
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index c0417cf17f..8c5800750f 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -93,12 +93,10 @@ avtab_insert_node(struct avtab *h, int hvalue,
newnode->next = prev->next;
prev->next = newnode;
} else {
- newnode->next = flex_array_get_ptr(h->htable, hvalue);
- if (flex_array_put_ptr(h->htable, hvalue, newnode,
- GFP_KERNEL|__GFP_ZERO)) {
- kmem_cache_free(avtab_node_cachep, newnode);
- return NULL;
- }
+ struct avtab_node **n = &h->htable[hvalue];
+
+ newnode->next = *n;
+ *n = newnode;
}
h->nel++;
@@ -111,11 +109,11 @@ static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_dat
struct avtab_node *prev, *cur, *newnode;
u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
- if (!h || !h->htable)
+ if (!h)
return -EINVAL;
hvalue = avtab_hash(key, h->mask);
- for (prev = NULL, cur = flex_array_get_ptr(h->htable, hvalue);
+ for (prev = NULL, cur = h->htable[hvalue];
cur;
prev = cur, cur = cur->next) {
if (key->source_type == cur->key.source_type &&
@@ -156,10 +154,10 @@ avtab_insert_nonunique(struct avtab *h, struct avtab_key *key, struct avtab_datu
struct avtab_node *prev, *cur;
u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
- if (!h || !h->htable)
+ if (!h)
return NULL;
hvalue = avtab_hash(key, h->mask);
- for (prev = NULL, cur = flex_array_get_ptr(h->htable, hvalue);
+ for (prev = NULL, cur = h->htable[hvalue];
cur;
prev = cur, cur = cur->next) {
if (key->source_type == cur->key.source_type &&
@@ -186,11 +184,11 @@ struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
struct avtab_node *cur;
u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
- if (!h || !h->htable)
+ if (!h)
return NULL;
hvalue = avtab_hash(key, h->mask);
- for (cur = flex_array_get_ptr(h->htable, hvalue); cur;
+ for (cur = h->htable[hvalue]; cur;
cur = cur->next) {
if (key->source_type == cur->key.source_type &&
key->target_type == cur->key.target_type &&
@@ -222,11 +220,11 @@ avtab_search_node(struct avtab *h, struct avtab_key *key)
struct avtab_node *cur;
u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
- if (!h || !h->htable)
+ if (!h)
return NULL;
hvalue = avtab_hash(key, h->mask);
- for (cur = flex_array_get_ptr(h->htable, hvalue); cur;
+ for (cur = h->htable[hvalue]; cur;
cur = cur->next) {
if (key->source_type == cur->key.source_type &&
key->target_type == cur->key.target_type &&
@@ -281,11 +279,11 @@ void avtab_destroy(struct avtab *h)
int i;
struct avtab_node *cur, *temp;
- if (!h || !h->htable)
+ if (!h)
return;
for (i = 0; i < h->nslot; i++) {
- cur = flex_array_get_ptr(h->htable, i);
+ cur = h->htable[i];
while (cur) {
temp = cur;
cur = cur->next;
@@ -295,7 +293,7 @@ void avtab_destroy(struct avtab *h)
kmem_cache_free(avtab_node_cachep, temp);
}
}
- flex_array_free(h->htable);
+ kvfree(h->htable);
h->htable = NULL;
h->nslot = 0;
h->mask = 0;
@@ -303,6 +301,7 @@ void avtab_destroy(struct avtab *h)
int avtab_init(struct avtab *h)
{
+ kvfree(h->htable);
h->htable = NULL;
h->nel = 0;
return 0;
@@ -329,8 +328,7 @@ int avtab_alloc(struct avtab *h, u32 nrules)
nslot = MAX_AVTAB_HASH_BUCKETS;
mask = nslot - 1;
- h->htable = flex_array_alloc(sizeof(struct avtab_node *), nslot,
- GFP_KERNEL | __GFP_ZERO);
+ h->htable = kvcalloc(nslot, sizeof(void *), GFP_KERNEL);
if (!h->htable)
return -ENOMEM;
@@ -353,7 +351,7 @@ void avtab_hash_eval(struct avtab *h, char *tag)
max_chain_len = 0;
chain2_len_sum = 0;
for (i = 0; i < h->nslot; i++) {
- cur = flex_array_get_ptr(h->htable, i);
+ cur = h->htable[i];
if (cur) {
slots_used++;
chain_len = 0;
@@ -646,7 +644,7 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp)
return rc;
for (i = 0; i < a->nslot; i++) {
- for (cur = flex_array_get_ptr(a->htable, i); cur;
+ for (cur = a->htable[i]; cur;
cur = cur->next) {
rc = avtab_write_item(p, cur, fp);
if (rc)
diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
index 0d652fad53..de16673b23 100644
--- a/security/selinux/ss/avtab.h
+++ b/security/selinux/ss/avtab.h
@@ -24,7 +24,6 @@
#define _SS_AVTAB_H_
#include "security.h"
-#include <linux/flex_array.h>
struct avtab_key {
u16 source_type; /* source type */
@@ -84,11 +83,10 @@ struct avtab_node {
};
struct avtab {
- struct flex_array *htable;
+ struct avtab_node **htable;
u32 nel; /* number of elements */
u32 nslot; /* number of hash slots */
u32 mask; /* mask to compute hash func */
-
};
int avtab_init(struct avtab *);
diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c
index f49e522e93..3bbb603452 100644
--- a/security/selinux/ss/conditional.c
+++ b/security/selinux/ss/conditional.c
@@ -195,7 +195,6 @@ int cond_index_bool(void *key, void *datum, void *datap)
{
struct policydb *p;
struct cond_bool_datum *booldatum;
- struct flex_array *fa;
booldatum = datum;
p = datap;
@@ -203,10 +202,7 @@ int cond_index_bool(void *key, void *datum, void *datap)
if (!booldatum->value || booldatum->value > p->p_bools.nprim)
return -EINVAL;
- fa = p->sym_val_to_name[SYM_BOOLS];
- if (flex_array_put_ptr(fa, booldatum->value - 1, key,
- GFP_KERNEL | __GFP_ZERO))
- BUG();
+ p->sym_val_to_name[SYM_BOOLS][booldatum->value - 1] = key;
p->bool_val_to_struct[booldatum->value - 1] = booldatum;
return 0;
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index f4eadd3f73..16b7027bb7 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -36,7 +36,6 @@
#include <linux/string.h>
#include <linux/errno.h>
#include <linux/audit.h>
-#include <linux/flex_array.h>
#include "security.h"
#include "policydb.h"
@@ -341,17 +340,14 @@ static int common_index(void *key, void *datum, void *datap)
{
struct policydb *p;
struct common_datum *comdatum;
- struct flex_array *fa;
comdatum = datum;
p = datap;
if (!comdatum->value || comdatum->value > p->p_commons.nprim)
return -EINVAL;
- fa = p->sym_val_to_name[SYM_COMMONS];
- if (flex_array_put_ptr(fa, comdatum->value - 1, key,
- GFP_KERNEL | __GFP_ZERO))
- BUG();
+ p->sym_val_to_name[SYM_COMMONS][comdatum->value - 1] = key;
+
return 0;
}
@@ -359,16 +355,13 @@ static int class_index(void *key, void *datum, void *datap)
{
struct policydb *p;
struct class_datum *cladatum;
- struct flex_array *fa;
cladatum = datum;
p = datap;
if (!cladatum->value || cladatum->value > p->p_classes.nprim)
return -EINVAL;
- fa = p->sym_val_to_name[SYM_CLASSES];
- if (flex_array_put_ptr(fa, cladatum->value - 1, key,
- GFP_KERNEL | __GFP_ZERO))
- BUG();
+
+ p->sym_val_to_name[SYM_CLASSES][cladatum->value - 1] = key;
p->class_val_to_struct[cladatum->value - 1] = cladatum;
return 0;
}
@@ -377,7 +370,6 @@ static int role_index(void *key, void *datum, void *datap)
{
struct policydb *p;
struct role_datum *role;
- struct flex_array *fa;
role = datum;
p = datap;
@@ -386,10 +378,7 @@ static int role_index(void *key, void *datum, void *datap)
|| role->bounds > p->p_roles.nprim)
return -EINVAL;
- fa = p->sym_val_to_name[SYM_ROLES];
- if (flex_array_put_ptr(fa, role->value - 1, key,
- GFP_KERNEL | __GFP_ZERO))
- BUG();
+ p->sym_val_to_name[SYM_ROLES][role->value - 1] = key;
p->role_val_to_struct[role->value - 1] = role;
return 0;
}
@@ -398,7 +387,6 @@ static int type_index(void *key, void *datum, void *datap)
{
struct policydb *p;
struct type_datum *typdatum;
- struct flex_array *fa;
typdatum = datum;
p = datap;
@@ -408,15 +396,8 @@ static int type_index(void *key, void *datum, void *datap)
|| typdatum->value > p->p_types.nprim
|| typdatum->bounds > p->p_types.nprim)
return -EINVAL;
- fa = p->sym_val_to_name[SYM_TYPES];
- if (flex_array_put_ptr(fa, typdatum->value - 1, key,
- GFP_KERNEL | __GFP_ZERO))
- BUG();
-
- fa = p->type_val_to_struct_array;
- if (flex_array_put_ptr(fa, typdatum->value - 1, typdatum,
- GFP_KERNEL | __GFP_ZERO))
- BUG();
+ p->sym_val_to_name[SYM_TYPES][typdatum->value - 1] = key;
+ p->type_val_to_struct_array[typdatum->value - 1] = typdatum;
}
return 0;
@@ -426,7 +407,6 @@ static int user_index(void *key, void *datum, void *datap)
{
struct policydb *p;
struct user_datum *usrdatum;
- struct flex_array *fa;
usrdatum = datum;
p = datap;
@@ -435,10 +415,7 @@ static int user_index(void *key, void *datum, void *datap)
|| usrdatum->bounds > p->p_users.nprim)
return -EINVAL;
- fa = p->sym_val_to_name[SYM_USERS];
- if (flex_array_put_ptr(fa, usrdatum->value - 1, key,
- GFP_KERNEL | __GFP_ZERO))
- BUG();
+ p->sym_val_to_name[SYM_USERS][usrdatum->value - 1] = key;
p->user_val_to_struct[usrdatum->value - 1] = usrdatum;
return 0;
}
@@ -447,7 +424,6 @@ static int sens_index(void *key, void *datum, void *datap)
{
struct policydb *p;
struct level_datum *levdatum;
- struct flex_array *fa;
levdatum = datum;
p = datap;
@@ -456,10 +432,8 @@ static int sens_index(void *key, void *datum, void *datap)
if (!levdatum->level->sens ||
levdatum->level->sens > p->p_levels.nprim)
return -EINVAL;
- fa = p->sym_val_to_name[SYM_LEVELS];
- if (flex_array_put_ptr(fa, levdatum->level->sens - 1, key,
- GFP_KERNEL | __GFP_ZERO))
- BUG();
+
+ p->sym_val_to_name[SYM_LEVELS][levdatum->level->sens - 1] = key;
}
return 0;
@@ -469,7 +443,6 @@ static int cat_index(void *key, void *datum, void *datap)
{
struct policydb *p;
struct cat_datum *catdatum;
- struct flex_array *fa;
catdatum = datum;
p = datap;
@@ -477,10 +450,8 @@ static int cat_index(void *key, void *datum, void *datap)
if (!catdatum->isalias) {
if (!catdatum->value || catdatum->value > p->p_cats.nprim)
return -EINVAL;
- fa = p->sym_val_to_name[SYM_CATS];
- if (flex_array_put_ptr(fa, catdatum->value - 1, key,
- GFP_KERNEL | __GFP_ZERO))
- BUG();
+
+ p->sym_val_to_name[SYM_CATS][catdatum->value - 1] = key;
}
return 0;
@@ -568,35 +539,23 @@ static int policydb_index(struct policydb *p)
if (!p->user_val_to_struct)
return -ENOMEM;
- /* Yes, I want the sizeof the pointer, not the structure */
- p->type_val_to_struct_array = flex_array_alloc(sizeof(struct type_datum *),
- p->p_types.nprim,
- GFP_KERNEL | __GFP_ZERO);
+ p->type_val_to_struct_array = kvcalloc(p->p_types.nprim,
+ sizeof(*p->type_val_to_struct_array),
+ GFP_KERNEL);
if (!p->type_val_to_struct_array)
return -ENOMEM;
- rc = flex_array_prealloc(p->type_val_to_struct_array, 0,
- p->p_types.nprim, GFP_KERNEL | __GFP_ZERO);
- if (rc)
- goto out;
-
rc = cond_init_bool_indexes(p);
if (rc)
goto out;
for (i = 0; i < SYM_NUM; i++) {
- p->sym_val_to_name[i] = flex_array_alloc(sizeof(char *),
- p->symtab[i].nprim,
- GFP_KERNEL | __GFP_ZERO);
+ p->sym_val_to_name[i] = kvcalloc(p->symtab[i].nprim,
+ sizeof(char *),
+ GFP_KERNEL);
if (!p->sym_val_to_name[i])
return -ENOMEM;
- rc = flex_array_prealloc(p->sym_val_to_name[i],
- 0, p->symtab[i].nprim,
- GFP_KERNEL | __GFP_ZERO);
- if (rc)
- goto out;
-
rc = hashtab_map(p->symtab[i].table, index_f[i], p);
if (rc)
goto out;
@@ -809,16 +768,13 @@ void policydb_destroy(struct policydb *p)
hashtab_destroy(p->symtab[i].table);
}
- for (i = 0; i < SYM_NUM; i++) {
- if (p->sym_val_to_name[i])
- flex_array_free(p->sym_val_to_name[i]);
- }
+ for (i = 0; i < SYM_NUM; i++)
+ kvfree(p->sym_val_to_name[i]);
kfree(p->class_val_to_struct);
kfree(p->role_val_to_struct);
kfree(p->user_val_to_struct);
- if (p->type_val_to_struct_array)
- flex_array_free(p->type_val_to_struct_array);
+ kvfree(p->type_val_to_struct_array);
avtab_destroy(&p->te_avtab);
@@ -871,17 +827,9 @@ void policydb_destroy(struct policydb *p)
hashtab_map(p->range_tr, range_tr_destroy, NULL);
hashtab_destroy(p->range_tr);
- if (p->type_attr_map_array) {
- for (i = 0; i < p->p_types.nprim; i++) {
- struct ebitmap *e;
-
- e = flex_array_get(p->type_attr_map_array, i);
- if (!e)
- continue;
- ebitmap_destroy(e);
- }
- flex_array_free(p->type_attr_map_array);
- }
+ for (i = 0; i < p->p_types.nprim; i++)
+ ebitmap_destroy(&p->type_attr_map_array[i]);
+ kvfree(p->type_attr_map_array);
ebitmap_destroy(&p->filename_trans_ttypes);
ebitmap_destroy(&p->policycaps);
@@ -1761,8 +1709,7 @@ static int type_bounds_sanity_check(void *key, void *datum, void *datap)
return -EINVAL;
}
- upper = flex_array_get_ptr(p->type_val_to_struct_array,
- upper->bounds - 1);
+ upper = p->type_val_to_struct_array[upper->bounds - 1];
BUG_ON(!upper);
if (upper->attribute) {
@@ -2519,23 +2466,15 @@ int policydb_read(struct policydb *p, void *fp)
if (rc)
goto bad;
- rc = -ENOMEM;
- p->type_attr_map_array = flex_array_alloc(sizeof(struct ebitmap),
- p->p_types.nprim,
- GFP_KERNEL | __GFP_ZERO);
+ p->type_attr_map_array = kvcalloc(p->p_types.nprim,
+ sizeof(*p->type_attr_map_array),
+ GFP_KERNEL);
if (!p->type_attr_map_array)
goto bad;
- /* preallocate so we don't have to worry about the put ever failing */
- rc = flex_array_prealloc(p->type_attr_map_array, 0, p->p_types.nprim,
- GFP_KERNEL | __GFP_ZERO);
- if (rc)
- goto bad;
-
for (i = 0; i < p->p_types.nprim; i++) {
- struct ebitmap *e = flex_array_get(p->type_attr_map_array, i);
+ struct ebitmap *e = &p->type_attr_map_array[i];
- BUG_ON(!e);
ebitmap_init(e);
if (p->policyvers >= POLICYDB_VERSION_AVTAB) {
rc = ebitmap_read(e, fp);
@@ -3524,9 +3463,8 @@ int policydb_write(struct policydb *p, void *fp)
return rc;
for (i = 0; i < p->p_types.nprim; i++) {
- struct ebitmap *e = flex_array_get(p->type_attr_map_array, i);
+ struct ebitmap *e = &p->type_attr_map_array[i];
- BUG_ON(!e);
rc = ebitmap_write(e, fp);
if (rc)
return rc;
diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
index 215f8f30ac..27039149ff 100644
--- a/security/selinux/ss/policydb.h
+++ b/security/selinux/ss/policydb.h
@@ -24,8 +24,6 @@
#ifndef _SS_POLICYDB_H_
#define _SS_POLICYDB_H_
-#include <linux/flex_array.h>
-
#include "symtab.h"
#include "avtab.h"
#include "sidtab.h"
@@ -251,13 +249,13 @@ struct policydb {
#define p_cats symtab[SYM_CATS]
/* symbol names indexed by (value - 1) */
- struct flex_array *sym_val_to_name[SYM_NUM];
+ char **sym_val_to_name[SYM_NUM];
/* class, role, and user attributes indexed by (value - 1) */
struct class_datum **class_val_to_struct;
struct role_datum **role_val_to_struct;
struct user_datum **user_val_to_struct;
- struct flex_array *type_val_to_struct_array;
+ struct type_datum **type_val_to_struct_array;
/* type enforcement access vectors and transitions */
struct avtab te_avtab;
@@ -294,7 +292,7 @@ struct policydb {
struct hashtab *range_tr;
/* type -> attribute reverse mapping */
- struct flex_array *type_attr_map_array;
+ struct ebitmap *type_attr_map_array;
struct ebitmap policycaps;
@@ -369,9 +367,7 @@ static inline int put_entry(const void *buf, size_t bytes, int num, struct polic
static inline char *sym_name(struct policydb *p, unsigned int sym_num, unsigned int element_nr)
{
- struct flex_array *fa = p->sym_val_to_name[sym_num];
-
- return flex_array_get_ptr(fa, element_nr);
+ return p->sym_val_to_name[sym_num][element_nr];
}
extern u16 string_to_security_class(struct policydb *p, const char *name);
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index 12e4143945..24b59a7e6a 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -50,7 +50,6 @@
#include <linux/audit.h>
#include <linux/mutex.h>
#include <linux/selinux.h>
-#include <linux/flex_array.h>
#include <linux/vmalloc.h>
#include <net/netlabel.h>
@@ -546,15 +545,13 @@ static void type_attribute_bounds_av(struct policydb *policydb,
struct type_datum *target;
u32 masked = 0;
- source = flex_array_get_ptr(policydb->type_val_to_struct_array,
- scontext->type - 1);
+ source = policydb->type_val_to_struct_array[scontext->type - 1];
BUG_ON(!source);
if (!source->bounds)
return;
- target = flex_array_get_ptr(policydb->type_val_to_struct_array,
- tcontext->type - 1);
+ target = policydb->type_val_to_struct_array[tcontext->type - 1];
BUG_ON(!target);
memset(&lo_avd, 0, sizeof(lo_avd));
@@ -654,11 +651,9 @@ static void context_struct_compute_av(struct policydb *policydb,
*/
avkey.target_class = tclass;
avkey.specified = AVTAB_AV | AVTAB_XPERMS;
- sattr = flex_array_get(policydb->type_attr_map_array,
- scontext->type - 1);
+ sattr = &policydb->type_attr_map_array[scontext->type - 1];
BUG_ON(!sattr);
- tattr = flex_array_get(policydb->type_attr_map_array,
- tcontext->type - 1);
+ tattr = &policydb->type_attr_map_array[tcontext->type - 1];
BUG_ON(!tattr);
ebitmap_for_each_positive_bit(sattr, snode, i) {
ebitmap_for_each_positive_bit(tattr, tnode, j) {
@@ -901,8 +896,7 @@ int security_bounded_transition(struct selinux_state *state,
index = new_context->type;
while (true) {
- type = flex_array_get_ptr(policydb->type_val_to_struct_array,
- index - 1);
+ type = policydb->type_val_to_struct_array[index - 1];
BUG_ON(!type);
/* not bounded anymore */
@@ -1065,11 +1059,9 @@ void security_compute_xperms_decision(struct selinux_state *state,
avkey.target_class = tclass;
avkey.specified = AVTAB_XPERMS;
- sattr = flex_array_get(policydb->type_attr_map_array,
- scontext->type - 1);
+ sattr = &policydb->type_attr_map_array[scontext->type - 1];
BUG_ON(!sattr);
- tattr = flex_array_get(policydb->type_attr_map_array,
- tcontext->type - 1);
+ tattr = &policydb->type_attr_map_array[tcontext->type - 1];
BUG_ON(!tattr);
ebitmap_for_each_positive_bit(sattr, snode, i) {
ebitmap_for_each_positive_bit(tattr, tnode, j) {
--
2.20.1
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 4/7] Generic radix trees
2018-12-17 13:19 [PATCH 0/7] generic radix trees; drop flex arrays Kent Overstreet
` (2 preceding siblings ...)
2018-12-17 13:19 ` [PATCH 3/7] selinux: " Kent Overstreet
@ 2018-12-17 13:19 ` Kent Overstreet
2018-12-17 13:19 ` [PATCH 5/7] proc: commit to genradix Kent Overstreet
` (2 subsequent siblings)
6 siblings, 0 replies; 15+ messages in thread
From: Kent Overstreet @ 2018-12-17 13:19 UTC (permalink / raw)
To: akpm, linux-kernel; +Cc: Kent Overstreet
Very simple radix tree implementation that supports storing arbitrary
size entries, up to PAGE_SIZE - upcoming patches will convert existing
flex_array users to genradixes. The new genradix code has a much simpler
API and implementation, and doesn't have a hard limit on the number of
elements like flex_array does.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
---
Documentation/core-api/generic-radix-tree.rst | 12 +
Documentation/core-api/index.rst | 1 +
include/linux/generic-radix-tree.h | 231 ++++++++++++++++++
lib/Makefile | 3 +-
lib/generic-radix-tree.c | 217 ++++++++++++++++
5 files changed, 463 insertions(+), 1 deletion(-)
create mode 100644 Documentation/core-api/generic-radix-tree.rst
create mode 100644 include/linux/generic-radix-tree.h
create mode 100644 lib/generic-radix-tree.c
diff --git a/Documentation/core-api/generic-radix-tree.rst b/Documentation/core-api/generic-radix-tree.rst
new file mode 100644
index 0000000000..80fd27440f
--- /dev/null
+++ b/Documentation/core-api/generic-radix-tree.rst
@@ -0,0 +1,12 @@
+=================================
+Generic radix trees/sparse arrays
+=================================
+
+.. kernel-doc:: include/linux/generic-radix-tree.h
+ :doc: Generic radix trees/sparse arrays
+
+generic radix tree functions
+----------------------------
+
+.. kernel-doc:: include/linux/generic-radix-tree.h
+ :functions:
diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst
index 3adee82be3..6870baffef 100644
--- a/Documentation/core-api/index.rst
+++ b/Documentation/core-api/index.rst
@@ -28,6 +28,7 @@ Core utilities
errseq
printk-formats
circular-buffers
+ generic-radix-tree
memory-allocation
mm-api
gfp_mask-from-fs-io
diff --git a/include/linux/generic-radix-tree.h b/include/linux/generic-radix-tree.h
new file mode 100644
index 0000000000..3a91130a4f
--- /dev/null
+++ b/include/linux/generic-radix-tree.h
@@ -0,0 +1,231 @@
+#ifndef _LINUX_GENERIC_RADIX_TREE_H
+#define _LINUX_GENERIC_RADIX_TREE_H
+
+/**
+ * DOC: Generic radix trees/sparse arrays:
+ *
+ * Very simple and minimalistic, supporting arbitrary size entries up to
+ * PAGE_SIZE.
+ *
+ * A genradix is defined with the type it will store, like so:
+ *
+ * static GENRADIX(struct foo) foo_genradix;
+ *
+ * The main operations are:
+ *
+ * - genradix_init(radix) - initialize an empty genradix
+ *
+ * - genradix_free(radix) - free all memory owned by the genradix and
+ * reinitialize it
+ *
+ * - genradix_ptr(radix, idx) - gets a pointer to the entry at idx, returning
+ * NULL if that entry does not exist
+ *
+ * - genradix_ptr_alloc(radix, idx, gfp) - gets a pointer to an entry,
+ * allocating it if necessary
+ *
+ * - genradix_for_each(radix, iter, p) - iterate over each entry in a genradix
+ *
+ * The radix tree allocates one page of entries at a time, so entries may exist
+ * that were never explicitly allocated - they will be initialized to all
+ * zeroes.
+ *
+ * Internally, a genradix is just a radix tree of pages, and indexing works in
+ * terms of byte offsets. The wrappers in this header file use sizeof on the
+ * type the radix contains to calculate a byte offset from the index - see
+ * __idx_to_offset.
+ */
+
+#include <asm/page.h>
+#include <linux/bug.h>
+#include <linux/kernel.h>
+#include <linux/log2.h>
+
+struct genradix_root;
+
+struct __genradix {
+ struct genradix_root __rcu *root;
+};
+
+/*
+ * NOTE: currently, sizeof(_type) must not be larger than PAGE_SIZE:
+ */
+
+#define __GENRADIX_INITIALIZER \
+ { \
+ .tree = { \
+ .root = NULL, \
+ } \
+ }
+
+/*
+ * We use a 0 size array to stash the type we're storing without taking any
+ * space at runtime - then the various accessor macros can use typeof() to get
+ * to it for casts/sizeof - we also force the alignment so that storing a type
+ * with a ridiculous alignment doesn't blow up the alignment or size of the
+ * genradix.
+ */
+
+#define GENRADIX(_type) \
+struct { \
+ struct __genradix tree; \
+ _type type[0] __aligned(1); \
+}
+
+#define DEFINE_GENRADIX(_name, _type) \
+ GENRADIX(_type) _name = __GENRADIX_INITIALIZER
+
+/**
+ * genradix_init - initialize a genradix
+ * @_radix: genradix to initialize
+ *
+ * Does not fail
+ */
+#define genradix_init(_radix) \
+do { \
+ *(_radix) = (typeof(*_radix)) __GENRADIX_INITIALIZER; \
+} while (0)
+
+void __genradix_free(struct __genradix *);
+
+/**
+ * genradix_free: free all memory owned by a genradix
+ * @_radix: the genradix to free
+ *
+ * After freeing, @_radix will be reinitialized and empty
+ */
+#define genradix_free(_radix) __genradix_free(&(_radix)->tree)
+
+static inline size_t __idx_to_offset(size_t idx, size_t obj_size)
+{
+ if (__builtin_constant_p(obj_size))
+ BUILD_BUG_ON(obj_size > PAGE_SIZE);
+ else
+ BUG_ON(obj_size > PAGE_SIZE);
+
+ if (!is_power_of_2(obj_size)) {
+ size_t objs_per_page = PAGE_SIZE / obj_size;
+
+ return (idx / objs_per_page) * PAGE_SIZE +
+ (idx % objs_per_page) * obj_size;
+ } else {
+ return idx * obj_size;
+ }
+}
+
+#define __genradix_cast(_radix) (typeof((_radix)->type[0]) *)
+#define __genradix_obj_size(_radix) sizeof((_radix)->type[0])
+#define __genradix_idx_to_offset(_radix, _idx) \
+ __idx_to_offset(_idx, __genradix_obj_size(_radix))
+
+void *__genradix_ptr(struct __genradix *, size_t);
+
+/**
+ * genradix_ptr - get a pointer to a genradix entry
+ * @_radix: genradix to access
+ * @_idx: index to fetch
+ *
+ * Returns a pointer to entry at @_idx, or NULL if that entry does not exist.
+ */
+#define genradix_ptr(_radix, _idx) \
+ (__genradix_cast(_radix) \
+ __genradix_ptr(&(_radix)->tree, \
+ __genradix_idx_to_offset(_radix, _idx)))
+
+void *__genradix_ptr_alloc(struct __genradix *, size_t, gfp_t);
+
+/**
+ * genradix_ptr_alloc - get a pointer to a genradix entry, allocating it
+ * if necessary
+ * @_radix: genradix to access
+ * @_idx: index to fetch
+ * @_gfp: gfp mask
+ *
+ * Returns a pointer to entry at @_idx, or NULL on allocation failure
+ */
+#define genradix_ptr_alloc(_radix, _idx, _gfp) \
+ (__genradix_cast(_radix) \
+ __genradix_ptr_alloc(&(_radix)->tree, \
+ __genradix_idx_to_offset(_radix, _idx), \
+ _gfp))
+
+struct genradix_iter {
+ size_t offset;
+ size_t pos;
+};
+
+/**
+ * genradix_iter_init - initialize a genradix_iter
+ * @_radix: genradix that will be iterated over
+ * @_idx: index to start iterating from
+ */
+#define genradix_iter_init(_radix, _idx) \
+ ((struct genradix_iter) { \
+ .pos = (_idx), \
+ .offset = __genradix_idx_to_offset((_radix), (_idx)),\
+ })
+
+void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t);
+
+/**
+ * genradix_iter_peek - get first entry at or above iterator's current
+ * position
+ * @_iter: a genradix_iter
+ * @_radix: genradix being iterated over
+ *
+ * If no more entries exist at or above @_iter's current position, returns NULL
+ */
+#define genradix_iter_peek(_iter, _radix) \
+ (__genradix_cast(_radix) \
+ __genradix_iter_peek(_iter, &(_radix)->tree, \
+ PAGE_SIZE / __genradix_obj_size(_radix)))
+
+static inline void __genradix_iter_advance(struct genradix_iter *iter,
+ size_t obj_size)
+{
+ iter->offset += obj_size;
+
+ if (!is_power_of_2(obj_size) &&
+ (iter->offset & (PAGE_SIZE - 1)) + obj_size > PAGE_SIZE)
+ iter->offset = round_up(iter->offset, PAGE_SIZE);
+
+ iter->pos++;
+}
+
+#define genradix_iter_advance(_iter, _radix) \
+ __genradix_iter_advance(_iter, __genradix_obj_size(_radix))
+
+#define genradix_for_each_from(_radix, _iter, _p, _start) \
+ for (_iter = genradix_iter_init(_radix, _start); \
+ (_p = genradix_iter_peek(&_iter, _radix)) != NULL; \
+ genradix_iter_advance(&_iter, _radix))
+
+/**
+ * genradix_for_each - iterate over entry in a genradix
+ * @_radix: genradix to iterate over
+ * @_iter: a genradix_iter to track current position
+ * @_p: pointer to genradix entry type
+ *
+ * On every iteration, @_p will point to the current entry, and @_iter.pos
+ * will be the current entry's index.
+ */
+#define genradix_for_each(_radix, _iter, _p) \
+ genradix_for_each_from(_radix, _iter, _p, 0)
+
+int __genradix_prealloc(struct __genradix *, size_t, gfp_t);
+
+/**
+ * genradix_prealloc - preallocate entries in a generic radix tree
+ * @_radix: genradix to preallocate
+ * @_nr: number of entries to preallocate
+ * @_gfp: gfp mask
+ *
+ * Returns 0 on success, -ENOMEM on failure
+ */
+#define genradix_prealloc(_radix, _nr, _gfp) \
+ __genradix_prealloc(&(_radix)->tree, \
+ __genradix_idx_to_offset(_radix, _nr + 1),\
+ _gfp)
+
+
+#endif /* _LINUX_GENERIC_RADIX_TREE_H */
diff --git a/lib/Makefile b/lib/Makefile
index db06d12378..f48beff23b 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -38,7 +38,8 @@ obj-y += bcd.o div64.o sort.o parser.o debug_locks.o random32.o \
gcd.o lcm.o list_sort.o uuid.o flex_array.o iov_iter.o clz_ctz.o \
bsearch.o find_bit.o llist.o memweight.o kfifo.o \
percpu-refcount.o rhashtable.o reciprocal_div.o \
- once.o refcount.o usercopy.o errseq.o bucket_locks.o
+ once.o refcount.o usercopy.o errseq.o bucket_locks.o \
+ generic-radix-tree.o
obj-$(CONFIG_STRING_SELFTEST) += test_string.o
obj-y += string_helpers.o
obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o
diff --git a/lib/generic-radix-tree.c b/lib/generic-radix-tree.c
new file mode 100644
index 0000000000..a7bafc4137
--- /dev/null
+++ b/lib/generic-radix-tree.c
@@ -0,0 +1,217 @@
+
+#include <linux/export.h>
+#include <linux/generic-radix-tree.h>
+#include <linux/gfp.h>
+
+#define GENRADIX_ARY (PAGE_SIZE / sizeof(struct genradix_node *))
+#define GENRADIX_ARY_SHIFT ilog2(GENRADIX_ARY)
+
+struct genradix_node {
+ union {
+ /* Interior node: */
+ struct genradix_node *children[GENRADIX_ARY];
+
+ /* Leaf: */
+ u8 data[PAGE_SIZE];
+ };
+};
+
+static inline int genradix_depth_shift(unsigned depth)
+{
+ return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth;
+}
+
+/*
+ * Returns size (of data, in bytes) that a tree of a given depth holds:
+ */
+static inline size_t genradix_depth_size(unsigned depth)
+{
+ return 1UL << genradix_depth_shift(depth);
+}
+
+/* depth that's needed for a genradix that can address up to ULONG_MAX: */
+#define GENRADIX_MAX_DEPTH \
+ DIV_ROUND_UP(BITS_PER_LONG - PAGE_SHIFT, GENRADIX_ARY_SHIFT)
+
+#define GENRADIX_DEPTH_MASK \
+ ((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1))
+
+unsigned genradix_root_to_depth(struct genradix_root *r)
+{
+ return (unsigned long) r & GENRADIX_DEPTH_MASK;
+}
+
+struct genradix_node *genradix_root_to_node(struct genradix_root *r)
+{
+ return (void *) ((unsigned long) r & ~GENRADIX_DEPTH_MASK);
+}
+
+/*
+ * Returns pointer to the specified byte @offset within @radix, or NULL if not
+ * allocated
+ */
+void *__genradix_ptr(struct __genradix *radix, size_t offset)
+{
+ struct genradix_root *r = READ_ONCE(radix->root);
+ struct genradix_node *n = genradix_root_to_node(r);
+ unsigned level = genradix_root_to_depth(r);
+
+ if (ilog2(offset) >= genradix_depth_shift(level))
+ return NULL;
+
+ while (1) {
+ if (!n)
+ return NULL;
+ if (!level)
+ break;
+
+ level--;
+
+ n = n->children[offset >> genradix_depth_shift(level)];
+ offset &= genradix_depth_size(level) - 1;
+ }
+
+ return &n->data[offset];
+}
+EXPORT_SYMBOL(__genradix_ptr);
+
+/*
+ * Returns pointer to the specified byte @offset within @radix, allocating it if
+ * necessary - newly allocated slots are always zeroed out:
+ */
+void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset,
+ gfp_t gfp_mask)
+{
+ struct genradix_root *v = READ_ONCE(radix->root);
+ struct genradix_node *n, *new_node = NULL;
+ unsigned level;
+
+ /* Increase tree depth if necessary: */
+ while (1) {
+ struct genradix_root *r = v, *new_root;
+
+ n = genradix_root_to_node(r);
+ level = genradix_root_to_depth(r);
+
+ if (n && ilog2(offset) < genradix_depth_shift(level))
+ break;
+
+ if (!new_node) {
+ new_node = (void *)
+ __get_free_page(gfp_mask|__GFP_ZERO);
+ if (!new_node)
+ return NULL;
+ }
+
+ new_node->children[0] = n;
+ new_root = ((struct genradix_root *)
+ ((unsigned long) new_node | (n ? level + 1 : 0)));
+
+ if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
+ v = new_root;
+ new_node = NULL;
+ }
+ }
+
+ while (level--) {
+ struct genradix_node **p =
+ &n->children[offset >> genradix_depth_shift(level)];
+ offset &= genradix_depth_size(level) - 1;
+
+ n = READ_ONCE(*p);
+ if (!n) {
+ if (!new_node) {
+ new_node = (void *)
+ __get_free_page(gfp_mask|__GFP_ZERO);
+ if (!new_node)
+ return NULL;
+ }
+
+ if (!(n = cmpxchg_release(p, NULL, new_node)))
+ swap(n, new_node);
+ }
+ }
+
+ if (new_node)
+ free_page((unsigned long) new_node);
+
+ return &n->data[offset];
+}
+EXPORT_SYMBOL(__genradix_ptr_alloc);
+
+void *__genradix_iter_peek(struct genradix_iter *iter,
+ struct __genradix *radix,
+ size_t objs_per_page)
+{
+ struct genradix_root *r;
+ struct genradix_node *n;
+ unsigned level, i;
+restart:
+ r = READ_ONCE(radix->root);
+ if (!r)
+ return NULL;
+
+ n = genradix_root_to_node(r);
+ level = genradix_root_to_depth(r);
+
+ if (ilog2(iter->offset) >= genradix_depth_shift(level))
+ return NULL;
+
+ while (level) {
+ level--;
+
+ i = (iter->offset >> genradix_depth_shift(level)) &
+ (GENRADIX_ARY - 1);
+
+ while (!n->children[i]) {
+ i++;
+ iter->offset = round_down(iter->offset +
+ genradix_depth_size(level),
+ genradix_depth_size(level));
+ iter->pos = (iter->offset >> PAGE_SHIFT) *
+ objs_per_page;
+ if (i == GENRADIX_ARY)
+ goto restart;
+ }
+
+ n = n->children[i];
+ }
+
+ return &n->data[iter->offset & (PAGE_SIZE - 1)];
+}
+EXPORT_SYMBOL(__genradix_iter_peek);
+
+static void genradix_free_recurse(struct genradix_node *n, unsigned level)
+{
+ if (level) {
+ unsigned i;
+
+ for (i = 0; i < GENRADIX_ARY; i++)
+ if (n->children[i])
+ genradix_free_recurse(n->children[i], level - 1);
+ }
+
+ free_page((unsigned long) n);
+}
+
+int __genradix_prealloc(struct __genradix *radix, size_t size,
+ gfp_t gfp_mask)
+{
+ size_t offset;
+
+ for (offset = 0; offset < size; offset += PAGE_SIZE)
+ if (!__genradix_ptr_alloc(radix, offset, gfp_mask))
+ return -ENOMEM;
+
+ return 0;
+}
+EXPORT_SYMBOL(__genradix_prealloc);
+
+void __genradix_free(struct __genradix *radix)
+{
+ struct genradix_root *r = xchg(&radix->root, NULL);
+
+ genradix_free_recurse(genradix_root_to_node(r),
+ genradix_root_to_depth(r));
+}
+EXPORT_SYMBOL(__genradix_free);
--
2.20.1
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 5/7] proc: commit to genradix
2018-12-17 13:19 [PATCH 0/7] generic radix trees; drop flex arrays Kent Overstreet
` (3 preceding siblings ...)
2018-12-17 13:19 ` [PATCH 4/7] Generic radix trees Kent Overstreet
@ 2018-12-17 13:19 ` Kent Overstreet
2018-12-17 13:19 ` [PATCH 6/7] sctp: Convert " Kent Overstreet
2018-12-17 13:19 ` [PATCH 7/7] Drop flex_arrays Kent Overstreet
6 siblings, 0 replies; 15+ messages in thread
From: Kent Overstreet @ 2018-12-17 13:19 UTC (permalink / raw)
To: akpm, linux-kernel; +Cc: Kent Overstreet, Al Viro
the new generic radix trees have a simpler API and implementation, and
no limitations on number of elements, so all flex_array users are being
converted
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Cc: Al Viro <viro@zeniv.linux.org.uk>
---
fs/proc/base.c | 43 +++++++++++++++----------------------------
1 file changed, 15 insertions(+), 28 deletions(-)
diff --git a/fs/proc/base.c b/fs/proc/base.c
index ce34654794..2edf386ed3 100644
--- a/fs/proc/base.c
+++ b/fs/proc/base.c
@@ -59,6 +59,7 @@
#include <linux/capability.h>
#include <linux/file.h>
#include <linux/fdtable.h>
+#include <linux/generic-radix-tree.h>
#include <linux/string.h>
#include <linux/seq_file.h>
#include <linux/namei.h>
@@ -92,7 +93,6 @@
#include <linux/sched/coredump.h>
#include <linux/sched/debug.h>
#include <linux/sched/stat.h>
-#include <linux/flex_array.h>
#include <linux/posix-timers.h>
#include <trace/events/oom.h>
#include "internal.h"
@@ -2140,11 +2140,12 @@ proc_map_files_readdir(struct file *file, struct dir_context *ctx)
struct task_struct *task;
struct mm_struct *mm;
unsigned long nr_files, pos, i;
- struct flex_array *fa = NULL;
- struct map_files_info info;
+ GENRADIX(struct map_files_info) fa;
struct map_files_info *p;
int ret;
+ genradix_init(&fa);
+
ret = -ENOENT;
task = get_proc_task(file_inode(file));
if (!task)
@@ -2176,35 +2177,22 @@ proc_map_files_readdir(struct file *file, struct dir_context *ctx)
*/
for (vma = mm->mmap, pos = 2; vma; vma = vma->vm_next) {
- if (vma->vm_file && ++pos > ctx->pos)
- nr_files++;
- }
+ if (!vma->vm_file)
+ continue;
+ if (++pos <= ctx->pos)
+ continue;
- if (nr_files) {
- fa = flex_array_alloc(sizeof(info), nr_files,
- GFP_KERNEL);
- if (!fa || flex_array_prealloc(fa, 0, nr_files,
- GFP_KERNEL)) {
+ p = genradix_ptr_alloc(&fa, nr_files++, GFP_KERNEL);
+ if (!p) {
ret = -ENOMEM;
- if (fa)
- flex_array_free(fa);
up_read(&mm->mmap_sem);
mmput(mm);
goto out_put_task;
}
- for (i = 0, vma = mm->mmap, pos = 2; vma;
- vma = vma->vm_next) {
- if (!vma->vm_file)
- continue;
- if (++pos <= ctx->pos)
- continue;
- info.start = vma->vm_start;
- info.end = vma->vm_end;
- info.mode = vma->vm_file->f_mode;
- if (flex_array_put(fa, i++, &info, GFP_KERNEL))
- BUG();
- }
+ p->start = vma->vm_start;
+ p->end = vma->vm_end;
+ p->mode = vma->vm_file->f_mode;
}
up_read(&mm->mmap_sem);
mmput(mm);
@@ -2213,7 +2201,7 @@ proc_map_files_readdir(struct file *file, struct dir_context *ctx)
char buf[4 * sizeof(long) + 2]; /* max: %lx-%lx\0 */
unsigned int len;
- p = flex_array_get(fa, i);
+ p = genradix_ptr(&fa, i);
len = snprintf(buf, sizeof(buf), "%lx-%lx", p->start, p->end);
if (!proc_fill_cache(file, ctx,
buf, len,
@@ -2223,12 +2211,11 @@ proc_map_files_readdir(struct file *file, struct dir_context *ctx)
break;
ctx->pos++;
}
- if (fa)
- flex_array_free(fa);
out_put_task:
put_task_struct(task);
out:
+ genradix_free(&fa);
return ret;
}
--
2.20.1
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 6/7] sctp: Convert to genradix
2018-12-17 13:19 [PATCH 0/7] generic radix trees; drop flex arrays Kent Overstreet
` (4 preceding siblings ...)
2018-12-17 13:19 ` [PATCH 5/7] proc: commit to genradix Kent Overstreet
@ 2018-12-17 13:19 ` Kent Overstreet
2018-12-17 20:50 ` Andrew Morton
2018-12-17 13:19 ` [PATCH 7/7] Drop flex_arrays Kent Overstreet
6 siblings, 1 reply; 15+ messages in thread
From: Kent Overstreet @ 2018-12-17 13:19 UTC (permalink / raw)
To: akpm, linux-kernel
Cc: Kent Overstreet, Vlad Yasevich, Neil Horman,
Marcelo Ricardo Leitner, linux-sctp
This also makes sctp_stream_alloc_(out|in) saner, in that they no longer
allocate new flex_arrays/genradixes, they just preallocate more
elements.
This code does however have a suspicious lack of locking.
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Cc: Vlad Yasevich <vyasevich@gmail.com>
Cc: Neil Horman <nhorman@tuxdriver.com>
Cc: Marcelo Ricardo Leitner <marcelo.leitner@gmail.com>
Cc: linux-sctp@vger.kernel.org
---
include/net/sctp/structs.h | 15 ++---
net/sctp/stream.c | 106 +++++++----------------------------
net/sctp/stream_interleave.c | 2 +-
3 files changed, 28 insertions(+), 95 deletions(-)
diff --git a/include/net/sctp/structs.h b/include/net/sctp/structs.h
index a11f937904..ee606e0fff 100644
--- a/include/net/sctp/structs.h
+++ b/include/net/sctp/structs.h
@@ -48,6 +48,7 @@
#define __sctp_structs_h__
#include <linux/ktime.h>
+#include <linux/generic-radix-tree.h>
#include <linux/rhashtable-types.h>
#include <linux/socket.h> /* linux/in.h needs this!! */
#include <linux/in.h> /* We get struct sockaddr_in. */
@@ -57,7 +58,6 @@
#include <linux/atomic.h> /* This gets us atomic counters. */
#include <linux/skbuff.h> /* We need sk_buff_head. */
#include <linux/workqueue.h> /* We need tq_struct. */
-#include <linux/flex_array.h> /* We need flex_array. */
#include <linux/sctp.h> /* We need sctp* header structs. */
#include <net/sctp/auth.h> /* We need auth specific structs */
#include <net/ip.h> /* For inet_skb_parm */
@@ -1441,8 +1441,9 @@ struct sctp_stream_in {
};
struct sctp_stream {
- struct flex_array *out;
- struct flex_array *in;
+ GENRADIX(struct sctp_stream_out) out;
+ GENRADIX(struct sctp_stream_in) in;
+
__u16 outcnt;
__u16 incnt;
/* Current stream being sent, if any */
@@ -1465,17 +1466,17 @@ struct sctp_stream {
};
static inline struct sctp_stream_out *sctp_stream_out(
- const struct sctp_stream *stream,
+ struct sctp_stream *stream,
__u16 sid)
{
- return flex_array_get(stream->out, sid);
+ return genradix_ptr(&stream->out, sid);
}
static inline struct sctp_stream_in *sctp_stream_in(
- const struct sctp_stream *stream,
+ struct sctp_stream *stream,
__u16 sid)
{
- return flex_array_get(stream->in, sid);
+ return genradix_ptr(&stream->in, sid);
}
#define SCTP_SO(s, i) sctp_stream_out((s), (i))
diff --git a/net/sctp/stream.c b/net/sctp/stream.c
index ffb940d3b5..09b9c7dc59 100644
--- a/net/sctp/stream.c
+++ b/net/sctp/stream.c
@@ -37,53 +37,6 @@
#include <net/sctp/sm.h>
#include <net/sctp/stream_sched.h>
-static struct flex_array *fa_alloc(size_t elem_size, size_t elem_count,
- gfp_t gfp)
-{
- struct flex_array *result;
- int err;
-
- result = flex_array_alloc(elem_size, elem_count, gfp);
- if (result) {
- err = flex_array_prealloc(result, 0, elem_count, gfp);
- if (err) {
- flex_array_free(result);
- result = NULL;
- }
- }
-
- return result;
-}
-
-static void fa_free(struct flex_array *fa)
-{
- if (fa)
- flex_array_free(fa);
-}
-
-static void fa_copy(struct flex_array *fa, struct flex_array *from,
- size_t index, size_t count)
-{
- void *elem;
-
- while (count--) {
- elem = flex_array_get(from, index);
- flex_array_put(fa, index, elem, 0);
- index++;
- }
-}
-
-static void fa_zero(struct flex_array *fa, size_t index, size_t count)
-{
- void *elem;
-
- while (count--) {
- elem = flex_array_get(fa, index);
- memset(elem, 0, fa->element_size);
- index++;
- }
-}
-
/* Migrates chunks from stream queues to new stream queues if needed,
* but not across associations. Also, removes those chunks to streams
* higher than the new max.
@@ -138,46 +91,32 @@ static void sctp_stream_outq_migrate(struct sctp_stream *stream,
static int sctp_stream_alloc_out(struct sctp_stream *stream, __u16 outcnt,
gfp_t gfp)
{
- struct flex_array *out;
- size_t elem_size = sizeof(struct sctp_stream_out);
-
- out = fa_alloc(elem_size, outcnt, gfp);
- if (!out)
- return -ENOMEM;
-
- if (stream->out) {
- fa_copy(out, stream->out, 0, min(outcnt, stream->outcnt));
- fa_free(stream->out);
- }
+ int ret;
- if (outcnt > stream->outcnt)
- fa_zero(out, stream->outcnt, (outcnt - stream->outcnt));
+ if (outcnt <= stream->outcnt)
+ return 0;
- stream->out = out;
+ ret = genradix_prealloc(&stream->out, outcnt, gfp);
+ if (ret)
+ return ret;
+ stream->outcnt = outcnt;
return 0;
}
static int sctp_stream_alloc_in(struct sctp_stream *stream, __u16 incnt,
gfp_t gfp)
{
- struct flex_array *in;
- size_t elem_size = sizeof(struct sctp_stream_in);
-
- in = fa_alloc(elem_size, incnt, gfp);
- if (!in)
- return -ENOMEM;
-
- if (stream->in) {
- fa_copy(in, stream->in, 0, min(incnt, stream->incnt));
- fa_free(stream->in);
- }
+ int ret;
- if (incnt > stream->incnt)
- fa_zero(in, stream->incnt, (incnt - stream->incnt));
+ if (incnt <= stream->incnt)
+ return 0;
- stream->in = in;
+ ret = genradix_prealloc(&stream->in, incnt, gfp);
+ if (ret)
+ return ret;
+ stream->incnt = incnt;
return 0;
}
@@ -204,7 +143,6 @@ int sctp_stream_init(struct sctp_stream *stream, __u16 outcnt, __u16 incnt,
if (ret)
goto out;
- stream->outcnt = outcnt;
for (i = 0; i < stream->outcnt; i++)
SCTP_SO(stream, i)->state = SCTP_STREAM_OPEN;
@@ -218,14 +156,11 @@ int sctp_stream_init(struct sctp_stream *stream, __u16 outcnt, __u16 incnt,
ret = sctp_stream_alloc_in(stream, incnt, gfp);
if (ret) {
sched->free(stream);
- fa_free(stream->out);
- stream->out = NULL;
+ genradix_free(&stream->out);
stream->outcnt = 0;
goto out;
}
- stream->incnt = incnt;
-
out:
return ret;
}
@@ -250,8 +185,8 @@ void sctp_stream_free(struct sctp_stream *stream)
sched->free(stream);
for (i = 0; i < stream->outcnt; i++)
kfree(SCTP_SO(stream, i)->ext);
- fa_free(stream->out);
- fa_free(stream->in);
+ genradix_free(&stream->out);
+ genradix_free(&stream->in);
}
void sctp_stream_clear(struct sctp_stream *stream)
@@ -282,8 +217,8 @@ void sctp_stream_update(struct sctp_stream *stream, struct sctp_stream *new)
sched->sched_all(stream);
- new->out = NULL;
- new->in = NULL;
+ new->out.tree.root = NULL;
+ new->in.tree.root = NULL;
new->outcnt = 0;
new->incnt = 0;
}
@@ -535,9 +470,6 @@ int sctp_send_add_streams(struct sctp_association *asoc,
goto out;
}
- stream->incnt = incnt;
- stream->outcnt = outcnt;
-
asoc->strreset_outstanding = !!out + !!in;
out:
diff --git a/net/sctp/stream_interleave.c b/net/sctp/stream_interleave.c
index 0a78cdf864..afada93d9f 100644
--- a/net/sctp/stream_interleave.c
+++ b/net/sctp/stream_interleave.c
@@ -101,7 +101,7 @@ static void sctp_chunk_assign_mid(struct sctp_chunk *chunk)
static bool sctp_validate_data(struct sctp_chunk *chunk)
{
- const struct sctp_stream *stream;
+ struct sctp_stream *stream;
__u16 sid, ssn;
if (chunk->chunk_hdr->type != SCTP_CID_DATA)
--
2.20.1
^ permalink raw reply related [flat|nested] 15+ messages in thread* Re: [PATCH 6/7] sctp: Convert to genradix
2018-12-17 13:19 ` [PATCH 6/7] sctp: Convert " Kent Overstreet
@ 2018-12-17 20:50 ` Andrew Morton
2018-12-17 20:59 ` Marcelo Ricardo Leitner
2018-12-17 21:00 ` Kent Overstreet
0 siblings, 2 replies; 15+ messages in thread
From: Andrew Morton @ 2018-12-17 20:50 UTC (permalink / raw)
To: Kent Overstreet
Cc: linux-kernel, Vlad Yasevich, Neil Horman, Marcelo Ricardo Leitner,
linux-sctp
On Mon, 17 Dec 2018 08:19:28 -0500 Kent Overstreet <kent.overstreet@gmail.com> wrote:
> @@ -535,9 +470,6 @@ int sctp_send_add_streams(struct sctp_association *asoc,
> goto out;
> }
>
> - stream->incnt = incnt;
> - stream->outcnt = outcnt;
> -
> asoc->strreset_outstanding = !!out + !!in;
>
I'm seeing a reject here for some reason. Using todays's linux-next,
but there are no changes against net/sctp/stream.c in -next. The
assignment to stream->incnt has disappeared. I did this:
@@ -535,8 +470,6 @@ int sctp_send_add_streams(struct sctp_as
goto out;
}
- stream->outcnt = outcnt;
-
asoc->strreset_outstanding = !!out + !!in;
out:
We're at 4.20-rc7 and this series is rather large. I'll merge them all
to see what happens, but I don't think it's 4.21-rc1 material?
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 6/7] sctp: Convert to genradix
2018-12-17 20:50 ` Andrew Morton
@ 2018-12-17 20:59 ` Marcelo Ricardo Leitner
2018-12-17 21:00 ` Kent Overstreet
1 sibling, 0 replies; 15+ messages in thread
From: Marcelo Ricardo Leitner @ 2018-12-17 20:59 UTC (permalink / raw)
To: Andrew Morton
Cc: Kent Overstreet, linux-kernel, Vlad Yasevich, Neil Horman,
linux-sctp
On Mon, Dec 17, 2018 at 12:50:01PM -0800, Andrew Morton wrote:
> On Mon, 17 Dec 2018 08:19:28 -0500 Kent Overstreet <kent.overstreet@gmail.com> wrote:
>
> > @@ -535,9 +470,6 @@ int sctp_send_add_streams(struct sctp_association *asoc,
> > goto out;
> > }
> >
> > - stream->incnt = incnt;
> > - stream->outcnt = outcnt;
> > -
> > asoc->strreset_outstanding = !!out + !!in;
> >
>
> I'm seeing a reject here for some reason. Using todays's linux-next,
> but there are no changes against net/sctp/stream.c in -next. The
> assignment to stream->incnt has disappeared. I did this:
>
> @@ -535,8 +470,6 @@ int sctp_send_add_streams(struct sctp_as
> goto out;
> }
>
> - stream->outcnt = outcnt;
> -
> asoc->strreset_outstanding = !!out + !!in;
>
> out:
That's because of
e1e46479847e ("sctp: not increase stream's incnt before sending addstrm_in request")
https://www.mail-archive.com/netdev@vger.kernel.org/msg255306.html
and what you did is the right merge fix for this.
>
>
> We're at 4.20-rc7 and this series is rather large. I'll merge them all
> to see what happens, but I don't think it's 4.21-rc1 material?
Would be nice to be conservative here. It's the first time this change
is being proposed for SCTP stack and testing was probably very
limited.
^ permalink raw reply [flat|nested] 15+ messages in thread* Re: [PATCH 6/7] sctp: Convert to genradix
2018-12-17 20:50 ` Andrew Morton
2018-12-17 20:59 ` Marcelo Ricardo Leitner
@ 2018-12-17 21:00 ` Kent Overstreet
2019-01-15 14:29 ` Marcelo Ricardo Leitner
1 sibling, 1 reply; 15+ messages in thread
From: Kent Overstreet @ 2018-12-17 21:00 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-kernel, Vlad Yasevich, Neil Horman, Marcelo Ricardo Leitner,
linux-sctp
On Mon, Dec 17, 2018 at 12:50:01PM -0800, Andrew Morton wrote:
> On Mon, 17 Dec 2018 08:19:28 -0500 Kent Overstreet <kent.overstreet@gmail.com> wrote:
>
> > @@ -535,9 +470,6 @@ int sctp_send_add_streams(struct sctp_association *asoc,
> > goto out;
> > }
> >
> > - stream->incnt = incnt;
> > - stream->outcnt = outcnt;
> > -
> > asoc->strreset_outstanding = !!out + !!in;
> >
>
> I'm seeing a reject here for some reason. Using todays's linux-next,
> but there are no changes against net/sctp/stream.c in -next. The
> assignment to stream->incnt has disappeared. I did this:
>
> @@ -535,8 +470,6 @@ int sctp_send_add_streams(struct sctp_as
> goto out;
> }
>
> - stream->outcnt = outcnt;
> -
> asoc->strreset_outstanding = !!out + !!in;
>
> out:
>
>
> We're at 4.20-rc7 and this series is rather large. I'll merge them all
> to see what happens, but I don't think it's 4.21-rc1 material?
Yeah, agreed. Thanks!
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 6/7] sctp: Convert to genradix
2018-12-17 21:00 ` Kent Overstreet
@ 2019-01-15 14:29 ` Marcelo Ricardo Leitner
2019-01-18 13:10 ` Neil Horman
0 siblings, 1 reply; 15+ messages in thread
From: Marcelo Ricardo Leitner @ 2019-01-15 14:29 UTC (permalink / raw)
To: Kent Overstreet
Cc: Andrew Morton, linux-kernel, Vlad Yasevich, Neil Horman,
linux-sctp
On Mon, Dec 17, 2018 at 04:00:21PM -0500, Kent Overstreet wrote:
> On Mon, Dec 17, 2018 at 12:50:01PM -0800, Andrew Morton wrote:
> > On Mon, 17 Dec 2018 08:19:28 -0500 Kent Overstreet <kent.overstreet@gmail.com> wrote:
> >
> > > @@ -535,9 +470,6 @@ int sctp_send_add_streams(struct sctp_association *asoc,
> > > goto out;
> > > }
> > >
> > > - stream->incnt = incnt;
> > > - stream->outcnt = outcnt;
> > > -
> > > asoc->strreset_outstanding = !!out + !!in;
> > >
> >
> > I'm seeing a reject here for some reason. Using todays's linux-next,
> > but there are no changes against net/sctp/stream.c in -next. The
> > assignment to stream->incnt has disappeared. I did this:
> >
> > @@ -535,8 +470,6 @@ int sctp_send_add_streams(struct sctp_as
> > goto out;
> > }
> >
> > - stream->outcnt = outcnt;
> > -
> > asoc->strreset_outstanding = !!out + !!in;
> >
> > out:
> >
> >
> > We're at 4.20-rc7 and this series is rather large. I'll merge them all
> > to see what happens, but I don't think it's 4.21-rc1 material?
>
> Yeah, agreed. Thanks!
Ping? Where did this go?
Marcelo
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 6/7] sctp: Convert to genradix
2019-01-15 14:29 ` Marcelo Ricardo Leitner
@ 2019-01-18 13:10 ` Neil Horman
2019-01-18 13:35 ` Marcelo Ricardo Leitner
0 siblings, 1 reply; 15+ messages in thread
From: Neil Horman @ 2019-01-18 13:10 UTC (permalink / raw)
To: Marcelo Ricardo Leitner
Cc: Kent Overstreet, Andrew Morton, linux-kernel, Vlad Yasevich,
linux-sctp
On Tue, Jan 15, 2019 at 12:29:26PM -0200, Marcelo Ricardo Leitner wrote:
> On Mon, Dec 17, 2018 at 04:00:21PM -0500, Kent Overstreet wrote:
> > On Mon, Dec 17, 2018 at 12:50:01PM -0800, Andrew Morton wrote:
> > > On Mon, 17 Dec 2018 08:19:28 -0500 Kent Overstreet <kent.overstreet@gmail.com> wrote:
> > >
> > > > @@ -535,9 +470,6 @@ int sctp_send_add_streams(struct sctp_association *asoc,
> > > > goto out;
> > > > }
> > > >
> > > > - stream->incnt = incnt;
> > > > - stream->outcnt = outcnt;
> > > > -
> > > > asoc->strreset_outstanding = !!out + !!in;
> > > >
> > >
> > > I'm seeing a reject here for some reason. Using todays's linux-next,
> > > but there are no changes against net/sctp/stream.c in -next. The
> > > assignment to stream->incnt has disappeared. I did this:
> > >
> > > @@ -535,8 +470,6 @@ int sctp_send_add_streams(struct sctp_as
> > > goto out;
> > > }
> > >
> > > - stream->outcnt = outcnt;
> > > -
> > > asoc->strreset_outstanding = !!out + !!in;
> > >
> > > out:
> > >
> > >
> > > We're at 4.20-rc7 and this series is rather large. I'll merge them all
> > > to see what happens, but I don't think it's 4.21-rc1 material?
> >
> > Yeah, agreed. Thanks!
>
> Ping? Where did this go?
>
As I recall kent reposted his series convirting flex_arrays to radix trees such
that it included sctp's uses.
I think xin needs to repost the sctp reallocation patch to make use of those
radix trees appropriately still (assuming any additional work still needs to be
done)
Neil
> Marcelo
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 6/7] sctp: Convert to genradix
2019-01-18 13:10 ` Neil Horman
@ 2019-01-18 13:35 ` Marcelo Ricardo Leitner
2019-01-18 14:51 ` Neil Horman
0 siblings, 1 reply; 15+ messages in thread
From: Marcelo Ricardo Leitner @ 2019-01-18 13:35 UTC (permalink / raw)
To: Neil Horman
Cc: Kent Overstreet, Andrew Morton, linux-kernel, Vlad Yasevich,
linux-sctp
On Fri, Jan 18, 2019 at 08:10:22AM -0500, Neil Horman wrote:
> On Tue, Jan 15, 2019 at 12:29:26PM -0200, Marcelo Ricardo Leitner wrote:
> > On Mon, Dec 17, 2018 at 04:00:21PM -0500, Kent Overstreet wrote:
> > > On Mon, Dec 17, 2018 at 12:50:01PM -0800, Andrew Morton wrote:
> > > > On Mon, 17 Dec 2018 08:19:28 -0500 Kent Overstreet <kent.overstreet@gmail.com> wrote:
> > > >
> > > > > @@ -535,9 +470,6 @@ int sctp_send_add_streams(struct sctp_association *asoc,
> > > > > goto out;
> > > > > }
> > > > >
> > > > > - stream->incnt = incnt;
> > > > > - stream->outcnt = outcnt;
> > > > > -
> > > > > asoc->strreset_outstanding = !!out + !!in;
> > > > >
> > > >
> > > > I'm seeing a reject here for some reason. Using todays's linux-next,
> > > > but there are no changes against net/sctp/stream.c in -next. The
> > > > assignment to stream->incnt has disappeared. I did this:
> > > >
> > > > @@ -535,8 +470,6 @@ int sctp_send_add_streams(struct sctp_as
> > > > goto out;
> > > > }
> > > >
> > > > - stream->outcnt = outcnt;
> > > > -
> > > > asoc->strreset_outstanding = !!out + !!in;
> > > >
> > > > out:
> > > >
> > > >
> > > > We're at 4.20-rc7 and this series is rather large. I'll merge them all
> > > > to see what happens, but I don't think it's 4.21-rc1 material?
> > >
> > > Yeah, agreed. Thanks!
> >
> > Ping? Where did this go?
> >
> As I recall kent reposted his series convirting flex_arrays to radix trees such
> that it included sctp's uses.
That should be this patchset already. Or you mean another (re)post,
v2 or so? If yes then I missed it somehow but I still see the
flex_array in v5.0-rc2:
net-next]$ git ls-tree v5.0-rc2 -- lib/flex_array.c
100644 blob 2eed22fa507c7cb0756d7ef643f8a3454eb455ec lib/flex_array.c
and missing the convertion on sctp stack.
Current patch is the only one I could find with sctp being included:
https://lore.kernel.org/lkml/20181217210021.GA7144@kmo-pixel/T/#re4f8656af37431a376044399681a8771375a4405
>
> I think xin needs to repost the sctp reallocation patch to make use of those
> radix trees appropriately still (assuming any additional work still needs to be
> done)
This came up on another converstation with him and the lack of this
convertion is blocking him on at least one fix, on one that the fix
using flex_arrays is one and genradix is another.
Marcelo
>
> Neil
>
> > Marcelo
> >
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 6/7] sctp: Convert to genradix
2019-01-18 13:35 ` Marcelo Ricardo Leitner
@ 2019-01-18 14:51 ` Neil Horman
0 siblings, 0 replies; 15+ messages in thread
From: Neil Horman @ 2019-01-18 14:51 UTC (permalink / raw)
To: Marcelo Ricardo Leitner
Cc: Kent Overstreet, Andrew Morton, linux-kernel, Vlad Yasevich,
linux-sctp
On Fri, Jan 18, 2019 at 11:35:34AM -0200, Marcelo Ricardo Leitner wrote:
> On Fri, Jan 18, 2019 at 08:10:22AM -0500, Neil Horman wrote:
> > On Tue, Jan 15, 2019 at 12:29:26PM -0200, Marcelo Ricardo Leitner wrote:
> > > On Mon, Dec 17, 2018 at 04:00:21PM -0500, Kent Overstreet wrote:
> > > > On Mon, Dec 17, 2018 at 12:50:01PM -0800, Andrew Morton wrote:
> > > > > On Mon, 17 Dec 2018 08:19:28 -0500 Kent Overstreet <kent.overstreet@gmail.com> wrote:
> > > > >
> > > > > > @@ -535,9 +470,6 @@ int sctp_send_add_streams(struct sctp_association *asoc,
> > > > > > goto out;
> > > > > > }
> > > > > >
> > > > > > - stream->incnt = incnt;
> > > > > > - stream->outcnt = outcnt;
> > > > > > -
> > > > > > asoc->strreset_outstanding = !!out + !!in;
> > > > > >
> > > > >
> > > > > I'm seeing a reject here for some reason. Using todays's linux-next,
> > > > > but there are no changes against net/sctp/stream.c in -next. The
> > > > > assignment to stream->incnt has disappeared. I did this:
> > > > >
> > > > > @@ -535,8 +470,6 @@ int sctp_send_add_streams(struct sctp_as
> > > > > goto out;
> > > > > }
> > > > >
> > > > > - stream->outcnt = outcnt;
> > > > > -
> > > > > asoc->strreset_outstanding = !!out + !!in;
> > > > >
> > > > > out:
> > > > >
> > > > >
> > > > > We're at 4.20-rc7 and this series is rather large. I'll merge them all
> > > > > to see what happens, but I don't think it's 4.21-rc1 material?
> > > >
> > > > Yeah, agreed. Thanks!
> > >
> > > Ping? Where did this go?
> > >
> > As I recall kent reposted his series convirting flex_arrays to radix trees such
> > that it included sctp's uses.
>
> That should be this patchset already. Or you mean another (re)post,
> v2 or so? If yes then I missed it somehow but I still see the
> flex_array in v5.0-rc2:
>
> net-next]$ git ls-tree v5.0-rc2 -- lib/flex_array.c
> 100644 blob 2eed22fa507c7cb0756d7ef643f8a3454eb455ec lib/flex_array.c
>
> and missing the convertion on sctp stack.
>
> Current patch is the only one I could find with sctp being included:
> https://lore.kernel.org/lkml/20181217210021.GA7144@kmo-pixel/T/#re4f8656af37431a376044399681a8771375a4405
>
Correct, and it doesn't seem to be included yet, though I acked Kents patch as I
recall. not sure what the hold up is at this point
Neil
> >
> > I think xin needs to repost the sctp reallocation patch to make use of those
> > radix trees appropriately still (assuming any additional work still needs to be
> > done)
>
> This came up on another converstation with him and the lack of this
> convertion is blocking him on at least one fix, on one that the fix
> using flex_arrays is one and genradix is another.
>
> Marcelo
>
> >
> > Neil
> >
> > > Marcelo
> > >
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 7/7] Drop flex_arrays
2018-12-17 13:19 [PATCH 0/7] generic radix trees; drop flex arrays Kent Overstreet
` (5 preceding siblings ...)
2018-12-17 13:19 ` [PATCH 6/7] sctp: Convert " Kent Overstreet
@ 2018-12-17 13:19 ` Kent Overstreet
6 siblings, 0 replies; 15+ messages in thread
From: Kent Overstreet @ 2018-12-17 13:19 UTC (permalink / raw)
To: akpm, linux-kernel; +Cc: Kent Overstreet, Dave Hansen
All existing users have been converted to generic radix trees
Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Acked-by: Dave Hansen <dave.hansen@intel.com>
---
Documentation/core-api/flexible-arrays.rst | 130 -------
Documentation/flexible-arrays.txt | 123 -------
include/linux/flex_array.h | 149 --------
include/linux/poison.h | 3 -
lib/Makefile | 2 +-
lib/flex_array.c | 398 ---------------------
tools/include/linux/poison.h | 3 -
7 files changed, 1 insertion(+), 807 deletions(-)
delete mode 100644 Documentation/core-api/flexible-arrays.rst
delete mode 100644 Documentation/flexible-arrays.txt
delete mode 100644 include/linux/flex_array.h
delete mode 100644 lib/flex_array.c
diff --git a/Documentation/core-api/flexible-arrays.rst b/Documentation/core-api/flexible-arrays.rst
deleted file mode 100644
index b6b85a1b51..0000000000
--- a/Documentation/core-api/flexible-arrays.rst
+++ /dev/null
@@ -1,130 +0,0 @@
-
-===================================
-Using flexible arrays in the kernel
-===================================
-
-Large contiguous memory allocations can be unreliable in the Linux kernel.
-Kernel programmers will sometimes respond to this problem by allocating
-pages with :c:func:`vmalloc()`. This solution not ideal, though. On 32-bit
-systems, memory from vmalloc() must be mapped into a relatively small address
-space; it's easy to run out. On SMP systems, the page table changes required
-by vmalloc() allocations can require expensive cross-processor interrupts on
-all CPUs. And, on all systems, use of space in the vmalloc() range increases
-pressure on the translation lookaside buffer (TLB), reducing the performance
-of the system.
-
-In many cases, the need for memory from vmalloc() can be eliminated by piecing
-together an array from smaller parts; the flexible array library exists to make
-this task easier.
-
-A flexible array holds an arbitrary (within limits) number of fixed-sized
-objects, accessed via an integer index. Sparse arrays are handled
-reasonably well. Only single-page allocations are made, so memory
-allocation failures should be relatively rare. The down sides are that the
-arrays cannot be indexed directly, individual object size cannot exceed the
-system page size, and putting data into a flexible array requires a copy
-operation. It's also worth noting that flexible arrays do no internal
-locking at all; if concurrent access to an array is possible, then the
-caller must arrange for appropriate mutual exclusion.
-
-The creation of a flexible array is done with :c:func:`flex_array_alloc()`::
-
- #include <linux/flex_array.h>
-
- struct flex_array *flex_array_alloc(int element_size,
- unsigned int total,
- gfp_t flags);
-
-The individual object size is provided by ``element_size``, while total is the
-maximum number of objects which can be stored in the array. The flags
-argument is passed directly to the internal memory allocation calls. With
-the current code, using flags to ask for high memory is likely to lead to
-notably unpleasant side effects.
-
-It is also possible to define flexible arrays at compile time with::
-
- DEFINE_FLEX_ARRAY(name, element_size, total);
-
-This macro will result in a definition of an array with the given name; the
-element size and total will be checked for validity at compile time.
-
-Storing data into a flexible array is accomplished with a call to
-:c:func:`flex_array_put()`::
-
- int flex_array_put(struct flex_array *array, unsigned int element_nr,
- void *src, gfp_t flags);
-
-This call will copy the data from src into the array, in the position
-indicated by ``element_nr`` (which must be less than the maximum specified when
-the array was created). If any memory allocations must be performed, flags
-will be used. The return value is zero on success, a negative error code
-otherwise.
-
-There might possibly be a need to store data into a flexible array while
-running in some sort of atomic context; in this situation, sleeping in the
-memory allocator would be a bad thing. That can be avoided by using
-``GFP_ATOMIC`` for the flags value, but, often, there is a better way. The
-trick is to ensure that any needed memory allocations are done before
-entering atomic context, using :c:func:`flex_array_prealloc()`::
-
- int flex_array_prealloc(struct flex_array *array, unsigned int start,
- unsigned int nr_elements, gfp_t flags);
-
-This function will ensure that memory for the elements indexed in the range
-defined by ``start`` and ``nr_elements`` has been allocated. Thereafter, a
-``flex_array_put()`` call on an element in that range is guaranteed not to
-block.
-
-Getting data back out of the array is done with :c:func:`flex_array_get()`::
-
- void *flex_array_get(struct flex_array *fa, unsigned int element_nr);
-
-The return value is a pointer to the data element, or NULL if that
-particular element has never been allocated.
-
-Note that it is possible to get back a valid pointer for an element which
-has never been stored in the array. Memory for array elements is allocated
-one page at a time; a single allocation could provide memory for several
-adjacent elements. Flexible array elements are normally initialized to the
-value ``FLEX_ARRAY_FREE`` (defined as 0x6c in <linux/poison.h>), so errors
-involving that number probably result from use of unstored array entries.
-Note that, if array elements are allocated with ``__GFP_ZERO``, they will be
-initialized to zero and this poisoning will not happen.
-
-Individual elements in the array can be cleared with
-:c:func:`flex_array_clear()`::
-
- int flex_array_clear(struct flex_array *array, unsigned int element_nr);
-
-This function will set the given element to ``FLEX_ARRAY_FREE`` and return
-zero. If storage for the indicated element is not allocated for the array,
-``flex_array_clear()`` will return ``-EINVAL`` instead. Note that clearing an
-element does not release the storage associated with it; to reduce the
-allocated size of an array, call :c:func:`flex_array_shrink()`::
-
- int flex_array_shrink(struct flex_array *array);
-
-The return value will be the number of pages of memory actually freed.
-This function works by scanning the array for pages containing nothing but
-``FLEX_ARRAY_FREE`` bytes, so (1) it can be expensive, and (2) it will not work
-if the array's pages are allocated with ``__GFP_ZERO``.
-
-It is possible to remove all elements of an array with a call to
-:c:func:`flex_array_free_parts()`::
-
- void flex_array_free_parts(struct flex_array *array);
-
-This call frees all elements, but leaves the array itself in place.
-Freeing the entire array is done with :c:func:`flex_array_free()`::
-
- void flex_array_free(struct flex_array *array);
-
-As of this writing, there are no users of flexible arrays in the mainline
-kernel. The functions described here are also not exported to modules;
-that will probably be fixed when somebody comes up with a need for it.
-
-
-Flexible array functions
-------------------------
-
-.. kernel-doc:: include/linux/flex_array.h
diff --git a/Documentation/flexible-arrays.txt b/Documentation/flexible-arrays.txt
deleted file mode 100644
index a0f2989dd8..0000000000
--- a/Documentation/flexible-arrays.txt
+++ /dev/null
@@ -1,123 +0,0 @@
-===================================
-Using flexible arrays in the kernel
-===================================
-
-:Updated: Last updated for 2.6.32
-:Author: Jonathan Corbet <corbet@lwn.net>
-
-Large contiguous memory allocations can be unreliable in the Linux kernel.
-Kernel programmers will sometimes respond to this problem by allocating
-pages with vmalloc(). This solution not ideal, though. On 32-bit systems,
-memory from vmalloc() must be mapped into a relatively small address space;
-it's easy to run out. On SMP systems, the page table changes required by
-vmalloc() allocations can require expensive cross-processor interrupts on
-all CPUs. And, on all systems, use of space in the vmalloc() range
-increases pressure on the translation lookaside buffer (TLB), reducing the
-performance of the system.
-
-In many cases, the need for memory from vmalloc() can be eliminated by
-piecing together an array from smaller parts; the flexible array library
-exists to make this task easier.
-
-A flexible array holds an arbitrary (within limits) number of fixed-sized
-objects, accessed via an integer index. Sparse arrays are handled
-reasonably well. Only single-page allocations are made, so memory
-allocation failures should be relatively rare. The down sides are that the
-arrays cannot be indexed directly, individual object size cannot exceed the
-system page size, and putting data into a flexible array requires a copy
-operation. It's also worth noting that flexible arrays do no internal
-locking at all; if concurrent access to an array is possible, then the
-caller must arrange for appropriate mutual exclusion.
-
-The creation of a flexible array is done with::
-
- #include <linux/flex_array.h>
-
- struct flex_array *flex_array_alloc(int element_size,
- unsigned int total,
- gfp_t flags);
-
-The individual object size is provided by element_size, while total is the
-maximum number of objects which can be stored in the array. The flags
-argument is passed directly to the internal memory allocation calls. With
-the current code, using flags to ask for high memory is likely to lead to
-notably unpleasant side effects.
-
-It is also possible to define flexible arrays at compile time with::
-
- DEFINE_FLEX_ARRAY(name, element_size, total);
-
-This macro will result in a definition of an array with the given name; the
-element size and total will be checked for validity at compile time.
-
-Storing data into a flexible array is accomplished with a call to::
-
- int flex_array_put(struct flex_array *array, unsigned int element_nr,
- void *src, gfp_t flags);
-
-This call will copy the data from src into the array, in the position
-indicated by element_nr (which must be less than the maximum specified when
-the array was created). If any memory allocations must be performed, flags
-will be used. The return value is zero on success, a negative error code
-otherwise.
-
-There might possibly be a need to store data into a flexible array while
-running in some sort of atomic context; in this situation, sleeping in the
-memory allocator would be a bad thing. That can be avoided by using
-GFP_ATOMIC for the flags value, but, often, there is a better way. The
-trick is to ensure that any needed memory allocations are done before
-entering atomic context, using::
-
- int flex_array_prealloc(struct flex_array *array, unsigned int start,
- unsigned int nr_elements, gfp_t flags);
-
-This function will ensure that memory for the elements indexed in the range
-defined by start and nr_elements has been allocated. Thereafter, a
-flex_array_put() call on an element in that range is guaranteed not to
-block.
-
-Getting data back out of the array is done with::
-
- void *flex_array_get(struct flex_array *fa, unsigned int element_nr);
-
-The return value is a pointer to the data element, or NULL if that
-particular element has never been allocated.
-
-Note that it is possible to get back a valid pointer for an element which
-has never been stored in the array. Memory for array elements is allocated
-one page at a time; a single allocation could provide memory for several
-adjacent elements. Flexible array elements are normally initialized to the
-value FLEX_ARRAY_FREE (defined as 0x6c in <linux/poison.h>), so errors
-involving that number probably result from use of unstored array entries.
-Note that, if array elements are allocated with __GFP_ZERO, they will be
-initialized to zero and this poisoning will not happen.
-
-Individual elements in the array can be cleared with::
-
- int flex_array_clear(struct flex_array *array, unsigned int element_nr);
-
-This function will set the given element to FLEX_ARRAY_FREE and return
-zero. If storage for the indicated element is not allocated for the array,
-flex_array_clear() will return -EINVAL instead. Note that clearing an
-element does not release the storage associated with it; to reduce the
-allocated size of an array, call::
-
- int flex_array_shrink(struct flex_array *array);
-
-The return value will be the number of pages of memory actually freed.
-This function works by scanning the array for pages containing nothing but
-FLEX_ARRAY_FREE bytes, so (1) it can be expensive, and (2) it will not work
-if the array's pages are allocated with __GFP_ZERO.
-
-It is possible to remove all elements of an array with a call to::
-
- void flex_array_free_parts(struct flex_array *array);
-
-This call frees all elements, but leaves the array itself in place.
-Freeing the entire array is done with::
-
- void flex_array_free(struct flex_array *array);
-
-As of this writing, there are no users of flexible arrays in the mainline
-kernel. The functions described here are also not exported to modules;
-that will probably be fixed when somebody comes up with a need for it.
diff --git a/include/linux/flex_array.h b/include/linux/flex_array.h
deleted file mode 100644
index b94fa61b51..0000000000
--- a/include/linux/flex_array.h
+++ /dev/null
@@ -1,149 +0,0 @@
-/* SPDX-License-Identifier: GPL-2.0 */
-#ifndef _FLEX_ARRAY_H
-#define _FLEX_ARRAY_H
-
-#include <linux/types.h>
-#include <linux/reciprocal_div.h>
-#include <asm/page.h>
-
-#define FLEX_ARRAY_PART_SIZE PAGE_SIZE
-#define FLEX_ARRAY_BASE_SIZE PAGE_SIZE
-
-struct flex_array_part;
-
-/*
- * This is meant to replace cases where an array-like
- * structure has gotten too big to fit into kmalloc()
- * and the developer is getting tempted to use
- * vmalloc().
- */
-
-struct flex_array {
- union {
- struct {
- int element_size;
- int total_nr_elements;
- int elems_per_part;
- struct reciprocal_value reciprocal_elems;
- struct flex_array_part *parts[];
- };
- /*
- * This little trick makes sure that
- * sizeof(flex_array) == PAGE_SIZE
- */
- char padding[FLEX_ARRAY_BASE_SIZE];
- };
-};
-
-/* Number of bytes left in base struct flex_array, excluding metadata */
-#define FLEX_ARRAY_BASE_BYTES_LEFT \
- (FLEX_ARRAY_BASE_SIZE - offsetof(struct flex_array, parts))
-
-/* Number of pointers in base to struct flex_array_part pages */
-#define FLEX_ARRAY_NR_BASE_PTRS \
- (FLEX_ARRAY_BASE_BYTES_LEFT / sizeof(struct flex_array_part *))
-
-/* Number of elements of size that fit in struct flex_array_part */
-#define FLEX_ARRAY_ELEMENTS_PER_PART(size) \
- (FLEX_ARRAY_PART_SIZE / size)
-
-/*
- * Defines a statically allocated flex array and ensures its parameters are
- * valid.
- */
-#define DEFINE_FLEX_ARRAY(__arrayname, __element_size, __total) \
- struct flex_array __arrayname = { { { \
- .element_size = (__element_size), \
- .total_nr_elements = (__total), \
- } } }; \
- static inline void __arrayname##_invalid_parameter(void) \
- { \
- BUILD_BUG_ON((__total) > FLEX_ARRAY_NR_BASE_PTRS * \
- FLEX_ARRAY_ELEMENTS_PER_PART(__element_size)); \
- }
-
-/**
- * flex_array_alloc() - Creates a flexible array.
- * @element_size: individual object size.
- * @total: maximum number of objects which can be stored.
- * @flags: GFP flags
- *
- * Return: Returns an object of structure flex_array.
- */
-struct flex_array *flex_array_alloc(int element_size, unsigned int total,
- gfp_t flags);
-
-/**
- * flex_array_prealloc() - Ensures that memory for the elements indexed in the
- * range defined by start and nr_elements has been allocated.
- * @fa: array to allocate memory to.
- * @start: start address
- * @nr_elements: number of elements to be allocated.
- * @flags: GFP flags
- *
- */
-int flex_array_prealloc(struct flex_array *fa, unsigned int start,
- unsigned int nr_elements, gfp_t flags);
-
-/**
- * flex_array_free() - Removes all elements of a flexible array.
- * @fa: array to be freed.
- */
-void flex_array_free(struct flex_array *fa);
-
-/**
- * flex_array_free_parts() - Removes all elements of a flexible array, but
- * leaves the array itself in place.
- * @fa: array to be emptied.
- */
-void flex_array_free_parts(struct flex_array *fa);
-
-/**
- * flex_array_put() - Stores data into a flexible array.
- * @fa: array where element is to be stored.
- * @element_nr: position to copy, must be less than the maximum specified when
- * the array was created.
- * @src: data source to be copied into the array.
- * @flags: GFP flags
- *
- * Return: Returns zero on success, a negative error code otherwise.
- */
-int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
- gfp_t flags);
-
-/**
- * flex_array_clear() - Clears an individual element in the array, sets the
- * given element to FLEX_ARRAY_FREE.
- * @element_nr: element position to clear.
- * @fa: array to which element to be cleared belongs.
- *
- * Return: Returns zero on success, -EINVAL otherwise.
- */
-int flex_array_clear(struct flex_array *fa, unsigned int element_nr);
-
-/**
- * flex_array_get() - Retrieves data into a flexible array.
- *
- * @element_nr: Element position to retrieve data from.
- * @fa: array from which data is to be retrieved.
- *
- * Return: Returns a pointer to the data element, or NULL if that
- * particular element has never been allocated.
- */
-void *flex_array_get(struct flex_array *fa, unsigned int element_nr);
-
-/**
- * flex_array_shrink() - Reduces the allocated size of an array.
- * @fa: array to shrink.
- *
- * Return: Returns number of pages of memory actually freed.
- *
- */
-int flex_array_shrink(struct flex_array *fa);
-
-#define flex_array_put_ptr(fa, nr, src, gfp) \
- flex_array_put(fa, nr, (void *)&(src), gfp)
-
-void *flex_array_get_ptr(struct flex_array *fa, unsigned int element_nr);
-
-#endif /* _FLEX_ARRAY_H */
diff --git a/include/linux/poison.h b/include/linux/poison.h
index 15927ebc22..10173f989a 100644
--- a/include/linux/poison.h
+++ b/include/linux/poison.h
@@ -83,9 +83,6 @@
#define MUTEX_DEBUG_FREE 0x22
#define MUTEX_POISON_WW_CTX ((void *) 0x500 + POISON_POINTER_DELTA)
-/********** lib/flex_array.c **********/
-#define FLEX_ARRAY_FREE 0x6c /* for use-after-free poisoning */
-
/********** security/ **********/
#define KEY_DESTROY 0xbd
diff --git a/lib/Makefile b/lib/Makefile
index f48beff23b..aa6dc8b890 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -35,7 +35,7 @@ obj-y += lockref.o
obj-y += bcd.o div64.o sort.o parser.o debug_locks.o random32.o \
bust_spinlocks.o kasprintf.o bitmap.o scatterlist.o \
- gcd.o lcm.o list_sort.o uuid.o flex_array.o iov_iter.o clz_ctz.o \
+ gcd.o lcm.o list_sort.o uuid.o iov_iter.o clz_ctz.o \
bsearch.o find_bit.o llist.o memweight.o kfifo.o \
percpu-refcount.o rhashtable.o reciprocal_div.o \
once.o refcount.o usercopy.o errseq.o bucket_locks.o \
diff --git a/lib/flex_array.c b/lib/flex_array.c
deleted file mode 100644
index 2eed22fa50..0000000000
--- a/lib/flex_array.c
+++ /dev/null
@@ -1,398 +0,0 @@
-/*
- * Flexible array managed in PAGE_SIZE parts
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
- *
- * Copyright IBM Corporation, 2009
- *
- * Author: Dave Hansen <dave@linux.vnet.ibm.com>
- */
-
-#include <linux/flex_array.h>
-#include <linux/slab.h>
-#include <linux/stddef.h>
-#include <linux/export.h>
-#include <linux/reciprocal_div.h>
-
-struct flex_array_part {
- char elements[FLEX_ARRAY_PART_SIZE];
-};
-
-/*
- * If a user requests an allocation which is small
- * enough, we may simply use the space in the
- * flex_array->parts[] array to store the user
- * data.
- */
-static inline int elements_fit_in_base(struct flex_array *fa)
-{
- int data_size = fa->element_size * fa->total_nr_elements;
- if (data_size <= FLEX_ARRAY_BASE_BYTES_LEFT)
- return 1;
- return 0;
-}
-
-/**
- * flex_array_alloc - allocate a new flexible array
- * @element_size: the size of individual elements in the array
- * @total: total number of elements that this should hold
- * @flags: page allocation flags to use for base array
- *
- * Note: all locking must be provided by the caller.
- *
- * @total is used to size internal structures. If the user ever
- * accesses any array indexes >=@total, it will produce errors.
- *
- * The maximum number of elements is defined as: the number of
- * elements that can be stored in a page times the number of
- * page pointers that we can fit in the base structure or (using
- * integer math):
- *
- * (PAGE_SIZE/element_size) * (PAGE_SIZE-8)/sizeof(void *)
- *
- * Here's a table showing example capacities. Note that the maximum
- * index that the get/put() functions is just nr_objects-1. This
- * basically means that you get 4MB of storage on 32-bit and 2MB on
- * 64-bit.
- *
- *
- * Element size | Objects | Objects |
- * PAGE_SIZE=4k | 32-bit | 64-bit |
- * ---------------------------------|
- * 1 bytes | 4177920 | 2088960 |
- * 2 bytes | 2088960 | 1044480 |
- * 3 bytes | 1392300 | 696150 |
- * 4 bytes | 1044480 | 522240 |
- * 32 bytes | 130560 | 65408 |
- * 33 bytes | 126480 | 63240 |
- * 2048 bytes | 2040 | 1020 |
- * 2049 bytes | 1020 | 510 |
- * void * | 1044480 | 261120 |
- *
- * Since 64-bit pointers are twice the size, we lose half the
- * capacity in the base structure. Also note that no effort is made
- * to efficiently pack objects across page boundaries.
- */
-struct flex_array *flex_array_alloc(int element_size, unsigned int total,
- gfp_t flags)
-{
- struct flex_array *ret;
- int elems_per_part = 0;
- int max_size = 0;
- struct reciprocal_value reciprocal_elems = { 0 };
-
- if (element_size) {
- elems_per_part = FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
- reciprocal_elems = reciprocal_value(elems_per_part);
- max_size = FLEX_ARRAY_NR_BASE_PTRS * elems_per_part;
- }
-
- /* max_size will end up 0 if element_size > PAGE_SIZE */
- if (total > max_size)
- return NULL;
- ret = kzalloc(sizeof(struct flex_array), flags);
- if (!ret)
- return NULL;
- ret->element_size = element_size;
- ret->total_nr_elements = total;
- ret->elems_per_part = elems_per_part;
- ret->reciprocal_elems = reciprocal_elems;
- if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO))
- memset(&ret->parts[0], FLEX_ARRAY_FREE,
- FLEX_ARRAY_BASE_BYTES_LEFT);
- return ret;
-}
-EXPORT_SYMBOL(flex_array_alloc);
-
-static int fa_element_to_part_nr(struct flex_array *fa,
- unsigned int element_nr)
-{
- /*
- * if element_size == 0 we don't get here, so we never touch
- * the zeroed fa->reciprocal_elems, which would yield invalid
- * results
- */
- return reciprocal_divide(element_nr, fa->reciprocal_elems);
-}
-
-/**
- * flex_array_free_parts - just free the second-level pages
- * @fa: the flex array from which to free parts
- *
- * This is to be used in cases where the base 'struct flex_array'
- * has been statically allocated and should not be free.
- */
-void flex_array_free_parts(struct flex_array *fa)
-{
- int part_nr;
-
- if (elements_fit_in_base(fa))
- return;
- for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++)
- kfree(fa->parts[part_nr]);
-}
-EXPORT_SYMBOL(flex_array_free_parts);
-
-void flex_array_free(struct flex_array *fa)
-{
- flex_array_free_parts(fa);
- kfree(fa);
-}
-EXPORT_SYMBOL(flex_array_free);
-
-static unsigned int index_inside_part(struct flex_array *fa,
- unsigned int element_nr,
- unsigned int part_nr)
-{
- unsigned int part_offset;
-
- part_offset = element_nr - part_nr * fa->elems_per_part;
- return part_offset * fa->element_size;
-}
-
-static struct flex_array_part *
-__fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags)
-{
- struct flex_array_part *part = fa->parts[part_nr];
- if (!part) {
- part = kmalloc(sizeof(struct flex_array_part), flags);
- if (!part)
- return NULL;
- if (!(flags & __GFP_ZERO))
- memset(part, FLEX_ARRAY_FREE,
- sizeof(struct flex_array_part));
- fa->parts[part_nr] = part;
- }
- return part;
-}
-
-/**
- * flex_array_put - copy data into the array at @element_nr
- * @fa: the flex array to copy data into
- * @element_nr: index of the position in which to insert
- * the new element.
- * @src: address of data to copy into the array
- * @flags: page allocation flags to use for array expansion
- *
- *
- * Note that this *copies* the contents of @src into
- * the array. If you are trying to store an array of
- * pointers, make sure to pass in &ptr instead of ptr.
- * You may instead wish to use the flex_array_put_ptr()
- * helper function.
- *
- * Locking must be provided by the caller.
- */
-int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
- gfp_t flags)
-{
- int part_nr = 0;
- struct flex_array_part *part;
- void *dst;
-
- if (element_nr >= fa->total_nr_elements)
- return -ENOSPC;
- if (!fa->element_size)
- return 0;
- if (elements_fit_in_base(fa))
- part = (struct flex_array_part *)&fa->parts[0];
- else {
- part_nr = fa_element_to_part_nr(fa, element_nr);
- part = __fa_get_part(fa, part_nr, flags);
- if (!part)
- return -ENOMEM;
- }
- dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
- memcpy(dst, src, fa->element_size);
- return 0;
-}
-EXPORT_SYMBOL(flex_array_put);
-
-/**
- * flex_array_clear - clear element in array at @element_nr
- * @fa: the flex array of the element.
- * @element_nr: index of the position to clear.
- *
- * Locking must be provided by the caller.
- */
-int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
-{
- int part_nr = 0;
- struct flex_array_part *part;
- void *dst;
-
- if (element_nr >= fa->total_nr_elements)
- return -ENOSPC;
- if (!fa->element_size)
- return 0;
- if (elements_fit_in_base(fa))
- part = (struct flex_array_part *)&fa->parts[0];
- else {
- part_nr = fa_element_to_part_nr(fa, element_nr);
- part = fa->parts[part_nr];
- if (!part)
- return -EINVAL;
- }
- dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
- memset(dst, FLEX_ARRAY_FREE, fa->element_size);
- return 0;
-}
-EXPORT_SYMBOL(flex_array_clear);
-
-/**
- * flex_array_prealloc - guarantee that array space exists
- * @fa: the flex array for which to preallocate parts
- * @start: index of first array element for which space is allocated
- * @nr_elements: number of elements for which space is allocated
- * @flags: page allocation flags
- *
- * This will guarantee that no future calls to flex_array_put()
- * will allocate memory. It can be used if you are expecting to
- * be holding a lock or in some atomic context while writing
- * data into the array.
- *
- * Locking must be provided by the caller.
- */
-int flex_array_prealloc(struct flex_array *fa, unsigned int start,
- unsigned int nr_elements, gfp_t flags)
-{
- int start_part;
- int end_part;
- int part_nr;
- unsigned int end;
- struct flex_array_part *part;
-
- if (!start && !nr_elements)
- return 0;
- if (start >= fa->total_nr_elements)
- return -ENOSPC;
- if (!nr_elements)
- return 0;
-
- end = start + nr_elements - 1;
-
- if (end >= fa->total_nr_elements)
- return -ENOSPC;
- if (!fa->element_size)
- return 0;
- if (elements_fit_in_base(fa))
- return 0;
- start_part = fa_element_to_part_nr(fa, start);
- end_part = fa_element_to_part_nr(fa, end);
- for (part_nr = start_part; part_nr <= end_part; part_nr++) {
- part = __fa_get_part(fa, part_nr, flags);
- if (!part)
- return -ENOMEM;
- }
- return 0;
-}
-EXPORT_SYMBOL(flex_array_prealloc);
-
-/**
- * flex_array_get - pull data back out of the array
- * @fa: the flex array from which to extract data
- * @element_nr: index of the element to fetch from the array
- *
- * Returns a pointer to the data at index @element_nr. Note
- * that this is a copy of the data that was passed in. If you
- * are using this to store pointers, you'll get back &ptr. You
- * may instead wish to use the flex_array_get_ptr helper.
- *
- * Locking must be provided by the caller.
- */
-void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
-{
- int part_nr = 0;
- struct flex_array_part *part;
-
- if (!fa->element_size)
- return NULL;
- if (element_nr >= fa->total_nr_elements)
- return NULL;
- if (elements_fit_in_base(fa))
- part = (struct flex_array_part *)&fa->parts[0];
- else {
- part_nr = fa_element_to_part_nr(fa, element_nr);
- part = fa->parts[part_nr];
- if (!part)
- return NULL;
- }
- return &part->elements[index_inside_part(fa, element_nr, part_nr)];
-}
-EXPORT_SYMBOL(flex_array_get);
-
-/**
- * flex_array_get_ptr - pull a ptr back out of the array
- * @fa: the flex array from which to extract data
- * @element_nr: index of the element to fetch from the array
- *
- * Returns the pointer placed in the flex array at element_nr using
- * flex_array_put_ptr(). This function should not be called if the
- * element in question was not set using the _put_ptr() helper.
- */
-void *flex_array_get_ptr(struct flex_array *fa, unsigned int element_nr)
-{
- void **tmp;
-
- tmp = flex_array_get(fa, element_nr);
- if (!tmp)
- return NULL;
-
- return *tmp;
-}
-EXPORT_SYMBOL(flex_array_get_ptr);
-
-static int part_is_free(struct flex_array_part *part)
-{
- int i;
-
- for (i = 0; i < sizeof(struct flex_array_part); i++)
- if (part->elements[i] != FLEX_ARRAY_FREE)
- return 0;
- return 1;
-}
-
-/**
- * flex_array_shrink - free unused second-level pages
- * @fa: the flex array to shrink
- *
- * Frees all second-level pages that consist solely of unused
- * elements. Returns the number of pages freed.
- *
- * Locking must be provided by the caller.
- */
-int flex_array_shrink(struct flex_array *fa)
-{
- struct flex_array_part *part;
- int part_nr;
- int ret = 0;
-
- if (!fa->total_nr_elements || !fa->element_size)
- return 0;
- if (elements_fit_in_base(fa))
- return ret;
- for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) {
- part = fa->parts[part_nr];
- if (!part)
- continue;
- if (part_is_free(part)) {
- fa->parts[part_nr] = NULL;
- kfree(part);
- ret++;
- }
- }
- return ret;
-}
-EXPORT_SYMBOL(flex_array_shrink);
diff --git a/tools/include/linux/poison.h b/tools/include/linux/poison.h
index 9fdcd3eaac..d297257691 100644
--- a/tools/include/linux/poison.h
+++ b/tools/include/linux/poison.h
@@ -87,9 +87,6 @@
#define MUTEX_DEBUG_INIT 0x11
#define MUTEX_DEBUG_FREE 0x22
-/********** lib/flex_array.c **********/
-#define FLEX_ARRAY_FREE 0x6c /* for use-after-free poisoning */
-
/********** security/ **********/
#define KEY_DESTROY 0xbd
--
2.20.1
^ permalink raw reply related [flat|nested] 15+ messages in thread