* Re: [RFC v3 1/7] hashtable: introduce a small and naive hashtable
From: Josh Triplett @ 2012-08-07 2:55 UTC (permalink / raw)
To: Sasha Levin
Cc: torvalds, tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem,
rostedt, mingo, ebiederm, aarcange, ericvh, netdev, eric.dumazet,
mathieu.desnoyers
In-Reply-To: <1344300317-23189-2-git-send-email-levinsasha928@gmail.com>
On Tue, Aug 07, 2012 at 02:45:10AM +0200, Sasha Levin wrote:
> +/**
> + * hash_add - add an object to a hashtable
> + * @hashtable: hashtable to add to
> + * @bits: bit count used for hashing
> + * @node: the &struct hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add(hashtable, bits, node, key) \
> + hlist_add_head(node, &hashtable[hash_min(key, bits)]);
Any particular reason to make this a macro rather than a static inline?
Also, even if you do make it a macro, don't include the semicolon.
> +/**
> + * hash_for_each_possible - iterate over all possible objects for a giver key
s/giver/given/
> + * @name: hashtable to iterate
> + * @obj: the type * to use as a loop cursor for each bucke
s/bucke/bucket/
- Josh Triplett
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply
* [PATCH] tc-tbf.8: Add parameter range to man page.
From: Li Wei @ 2012-08-07 2:30 UTC (permalink / raw)
To: shemminger; +Cc: netdev, Li Wei
Signed-off-by: Li Wei <lw@cn.fujitsu.com>
---
man/man8/tc-tbf.8 | 6 ++++++
1 file changed, 6 insertions(+)
diff --git a/man/man8/tc-tbf.8 b/man/man8/tc-tbf.8
index 3abb238..7b76146 100644
--- a/man/man8/tc-tbf.8
+++ b/man/man8/tc-tbf.8
@@ -76,6 +76,7 @@ latency parameter, which specifies the maximum amount of time a packet can
sit in the TBF. The latter calculation takes into account the size of the
bucket, the rate and possibly the peakrate (if set). These two parameters
are mutually exclusive.
+The range of parameter limit is [1, UINT32_MAX] bytes.
.TP
burst
Also known as buffer or maxburst.
@@ -85,6 +86,7 @@ if you want to reach your configured rate!
If your buffer is too small, packets may be dropped because more tokens arrive per timer tick than fit in your bucket.
The minimum buffer size can be calculated by dividing the rate by HZ.
+The range of this parameter is [1, UINT32_MAX] bytes.
Token usage calculations are performed using a table which by default has a resolution of 8 packets.
This resolution can be changed by specifying the
@@ -96,11 +98,13 @@ this. Must be an integral power of 2.
mpu
A zero-sized packet does not use zero bandwidth. For ethernet, no packet uses less than 64 bytes. The Minimum Packet Unit
determines the minimal token usage (specified in bytes) for a packet. Defaults to zero.
+The range of this parameter is [0, UINT32_MAX] bytes.
.TP
rate
The speed knob. See remarks above about limits! See
.BR tc (8)
for units.
+The range of this parameter is [1, UINT32_MAX] bps.
.PP
Furthermore, if a peakrate is desired, the following parameters are available:
@@ -108,12 +112,14 @@ Furthermore, if a peakrate is desired, the following parameters are available:
peakrate
Maximum depletion rate of the bucket. Limited to 1mbit/s on Intel, 10mbit/s on Alpha. The peakrate does
not need to be set, it is only necessary if perfect millisecond timescale shaping is required.
+The range of this parameter is [1, UINT32_MAX] bps.
.TP
mtu/minburst
Specifies the size of the peakrate bucket. For perfect accuracy, should be set to the MTU of the interface.
If a peakrate is needed, but some burstiness is acceptable, this size can be raised. A 3000 byte minburst
allows around 3mbit/s of peakrate, given 1000 byte packets.
+The range of this parameter is [1, UINT32_MAX] bytes.
Like the regular burstsize you can also specify a
.B cell
--
1.7.10.1
^ permalink raw reply related
* Re: [PATCH 1/8] netpoll: use GFP_ATOMIC in slave_enable_netpoll() and __netpoll_setup()
From: Cong Wang @ 2012-08-07 2:28 UTC (permalink / raw)
To: Eric Dumazet; +Cc: netdev, David S. Miller
In-Reply-To: <1344266405.26674.30.camel@edumazet-glaptop>
On Mon, 2012-08-06 at 17:20 +0200, Eric Dumazet wrote:
> On Mon, 2012-08-06 at 22:23 +0800, Cong Wang wrote:
> > slave_enable_netpoll() and __netpoll_setup() may be called
> > with read_lock() held, so should use GFP_ATOMIC to allocate
> > memory. Eric suggested to pass gfp flags to __netpoll_setup().
> >
> > Cc: Eric Dumazet <eric.dumazet@gmail.com>
> > Cc: "David S. Miller" <davem@davemloft.net>
> > Reported-by: Dan Carpenter <dan.carpenter@oracle.com>
> > Signed-off-by: Cong Wang <amwang@redhat.com>
> > ---
>
> You based this on net-next, but didnt add the net-next suffix in your
> [PATCH ...] description.
>
> Signed-off-by: Eric Dumazet <edumazet@google.com>
>
Oh, it is default, isn't it? :-D Anyway, I will add it the next time
when I send network patches.
Thanks!
^ permalink raw reply
* Re: [PATCH 7/8] bridge: add some comments for NETDEV_RELEASE
From: Cong Wang @ 2012-08-07 2:27 UTC (permalink / raw)
To: David Miller; +Cc: netdev, shemminger
In-Reply-To: <20120806.135003.442648448779232464.davem@davemloft.net>
On Mon, 2012-08-06 at 13:50 -0700, David Miller wrote:
> From: Cong Wang <amwang@redhat.com>
> Date: Mon, 6 Aug 2012 22:23:31 +0800
>
> > + /*
> > + * We don't notify NETDEV_RELEASE event, as this will
> > + * stop netconsole on the bridge.
> > + */
>
> Please format comments in the networking:
>
> /* Like
> * this.
> */
>
> Thanks.
Ok, I will update and resend this single patch. :)
^ permalink raw reply
* [PATCH] af_packet: Quiet sparse noise about using plain integer as NULL pointer
From: Ying Xue @ 2012-08-07 2:27 UTC (permalink / raw)
To: davem; +Cc: netdev
Quiets the sparse warning:
warning: Using plain integer as NULL pointer
Signed-off-by: Ying Xue <ying.xue@windriver.com>
---
net/packet/af_packet.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/net/packet/af_packet.c b/net/packet/af_packet.c
index ceaca7c..f016f66 100644
--- a/net/packet/af_packet.c
+++ b/net/packet/af_packet.c
@@ -1079,7 +1079,7 @@ static void *packet_current_rx_frame(struct packet_sock *po,
default:
WARN(1, "TPACKET version not supported\n");
BUG();
- return 0;
+ return NULL;
}
}
--
1.7.1
^ permalink raw reply related
* [RESEND][PATCH] drivers: net: irda: bfin_sir: fix compile error
From: Bob Liu @ 2012-08-07 2:08 UTC (permalink / raw)
To: davem
Cc: samuel, rmk+kernel, gregkh, kuninori.morimoto.gx, linux-kernel,
uclinux-dist-devel, netdev, Sonic Zhang, Bob Liu
From: Sonic Zhang <sonic.zhang@analog.com>
Bit IREN is replaced by UMOD_IRDA and UMOD_MASK since blackfin 60x added, but
this driver didn't update which will cause bfin_sir build error:
drivers/net/irda/bfin_sir.c:161:9: error: 'IREN' undeclared (first use in this
function)
drivers/net/irda/bfin_sir.c:435:18: error: 'IREN' undeclared (first use in
this function)
drivers/net/irda/bfin_sir.c:521:11: error: 'IREN' undeclared (first use in
this function)
This patch fix it.
Signed-off-by: Sonic Zhang <sonic.zhang@analog.com>
Signed-off-by: Bob Liu <lliubbo@gmail.com>
Acked-by: Samuel Ortiz <samuel@sortiz.org>
---
drivers/net/irda/bfin_sir.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
diff --git a/drivers/net/irda/bfin_sir.c b/drivers/net/irda/bfin_sir.c
index a561ae4..c6a0299 100644
--- a/drivers/net/irda/bfin_sir.c
+++ b/drivers/net/irda/bfin_sir.c
@@ -158,7 +158,7 @@ static int bfin_sir_set_speed(struct bfin_sir_port *port, int speed)
/* If not add the 'RPOLC', we can't catch the receive interrupt.
* It's related with the HW layout and the IR transiver.
*/
- val |= IREN | RPOLC;
+ val |= UMOD_IRDA | RPOLC;
UART_PUT_GCTL(port, val);
return ret;
}
@@ -432,7 +432,7 @@ static void bfin_sir_shutdown(struct bfin_sir_port *port, struct net_device *dev
bfin_sir_stop_rx(port);
val = UART_GET_GCTL(port);
- val &= ~(UCEN | IREN | RPOLC);
+ val &= ~(UCEN | UMOD_MASK | RPOLC);
UART_PUT_GCTL(port, val);
#ifdef CONFIG_SIR_BFIN_DMA
@@ -518,10 +518,10 @@ static void bfin_sir_send_work(struct work_struct *work)
* reset all the UART.
*/
val = UART_GET_GCTL(port);
- val &= ~(IREN | RPOLC);
+ val &= ~(UMOD_MASK | RPOLC);
UART_PUT_GCTL(port, val);
SSYNC();
- val |= IREN | RPOLC;
+ val |= UMOD_IRDA | RPOLC;
UART_PUT_GCTL(port, val);
SSYNC();
/* bfin_sir_set_speed(port, self->speed); */
--
1.7.9.5
^ permalink raw reply related
* Re: [RFC v3 1/7] hashtable: introduce a small and naive hashtable
From: Sasha Levin @ 2012-08-07 1:54 UTC (permalink / raw)
To: Li Wei
Cc: torvalds, tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem,
rostedt, mingo, ebiederm, aarcange, ericvh, netdev, josh,
eric.dumazet, mathieu.desnoyers
In-Reply-To: <502073E9.8050205@cn.fujitsu.com>
On 08/07/2012 03:48 AM, Li Wei wrote:
> On 08/07/2012 08:45 AM, Sasha Levin wrote:
>> +/**
>> + * hash_for_each - iterate over a hashtable
>> + * @name: hashtable to iterate
>> + * @bits: bit count of hashing function of the hashtable
>> + * @bkt: integer to use as bucket loop cursor
>> + * @node: the &struct list_head to use as a loop cursor for each bucket
>> + * @obj: the type * to use as a loop cursor for each bucket
>> + * @member: the name of the hlist_node within the struct
>> + */
>> +#define hash_for_each(name, bits, bkt, node, obj, member) \
>> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
>> + hlist_for_each_entry(obj, node, &name[i], member)
>
> Where is the 'i' coming from? maybe &name[bkt]?
Heh, yeah. And the only place that uses this macro had 'i' declared as the loop counter, so it didn't trigger any issues during testing.
Thanks!
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply
* Re: [RFC v3 1/7] hashtable: introduce a small and naive hashtable
From: Li Wei @ 2012-08-07 1:48 UTC (permalink / raw)
To: Sasha Levin
Cc: torvalds, tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem,
rostedt, mingo, ebiederm, aarcange, ericvh, netdev, josh,
eric.dumazet, mathieu.desnoyers
In-Reply-To: <1344300317-23189-2-git-send-email-levinsasha928@gmail.com>
On 08/07/2012 08:45 AM, Sasha Levin wrote:
> This hashtable implementation is using hlist buckets to provide a simple
> hashtable to prevent it from getting reimplemented all over the kernel.
>
> Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
> ---
> include/linux/hashtable.h | 82 +++++++++++++++++++++++++++++++++++++++++++++
> 1 files changed, 82 insertions(+), 0 deletions(-)
> create mode 100644 include/linux/hashtable.h
>
> diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
> new file mode 100644
> index 0000000..394652b
> --- /dev/null
> +++ b/include/linux/hashtable.h
> @@ -0,0 +1,82 @@
> +/*
> + * Hash table implementation
> + * (C) 2012 Sasha Levin <levinsasha928@gmail.com>
> + */
> +
> +#ifndef _LINUX_HASHTABLE_H
> +#define _LINUX_HASHTABLE_H
> +
> +#include <linux/list.h>
> +#include <linux/types.h>
> +#include <linux/kernel.h>
> +#include <linux/hash.h>
> +
> +#define DEFINE_HASHTABLE(name, bits) \
> + struct hlist_head name[HASH_SIZE(bits)];
> +
> +#define HASH_SIZE(bits) (1 << (bits))
> +
> +/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
> +#define hash_min(val, bits) ((sizeof(val)==4)?hash_32((val), (bits)):hash_long((val), (bits)))
> +
> +/**
> + * hash_init - initialize a hash table
> + * @hashtable: hashtable to be initialized
> + * @bits: bit count of hashing function
> + *
> + * Initializes a hash table with 2**bits buckets.
> + */
> +static inline void hash_init(struct hlist_head *hashtable, int bits)
> +{
> + int i;
> +
> + for (i = 0; i < HASH_SIZE(bits); i++)
> + INIT_HLIST_HEAD(hashtable + i);
> +}
> +
> +/**
> + * hash_add - add an object to a hashtable
> + * @hashtable: hashtable to add to
> + * @bits: bit count used for hashing
> + * @node: the &struct hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add(hashtable, bits, node, key) \
> + hlist_add_head(node, &hashtable[hash_min(key, bits)]);
> +
> +/**
> + * hash_del - remove an object from a hashtable
> + * @node: &struct hlist_node of the object to remove
> + */
> +static inline void hash_del(struct hlist_node *node)
> +{
> + hlist_del_init(node);
> +}
> +
> +/**
> + * hash_for_each - iterate over a hashtable
> + * @name: hashtable to iterate
> + * @bits: bit count of hashing function of the hashtable
> + * @bkt: integer to use as bucket loop cursor
> + * @node: the &struct list_head to use as a loop cursor for each bucket
> + * @obj: the type * to use as a loop cursor for each bucket
> + * @member: the name of the hlist_node within the struct
> + */
> +#define hash_for_each(name, bits, bkt, node, obj, member) \
> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
> + hlist_for_each_entry(obj, node, &name[i], member)
Where is the 'i' coming from? maybe &name[bkt]?
> +
> +/**
> + * hash_for_each_possible - iterate over all possible objects for a giver key
> + * @name: hashtable to iterate
> + * @obj: the type * to use as a loop cursor for each bucke
> + * @bits: bit count of hashing function of the hashtable
> + * @node: the &struct list_head to use as a loop cursor for each bucket
> + * @member: the name of the hlist_node within the struct
> + * @key: the key of the objects to iterate over
> + */
> +#define hash_for_each_possible(name, obj, bits, node, member, key) \
> + hlist_for_each_entry(obj, node, \
> + &name[hash_min(key, bits)], member)
> +
> +#endif
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply
* First pass at MSG_FASTOPEN support in top-of-trunk netperf
From: Rick Jones @ 2012-08-07 1:47 UTC (permalink / raw)
To: netdev
Folks -
I have just checked-in to the top-of-trunk netperf
(http://www.netperf.org/svn/netperf2/trunk) some changes which enable
use of sendto(MSG_FASTOPEN) in a TCP_CRR test. While I was checking the
system calls I noticed that netperf was calling enable_enobufs() for
every migrated test, not just a UDP_STREAM test (the one where it is
needed), so I fixed that at the same time. Baseline is taken with the
fix in place.
MSG_FASTOPEN is used when one adds a test-specific -F option to the
netperf command line:
netperf -t TCP_CRR -H <destination> -- -F
Just testing the client side from a VM on my workstation (running a
net-next pulled just before 16:30 Pacific time) to my workstation itself
I notice the following:
Without MSG_FASTOPEN:
raj@tardy-ubuntu-1204:~/netperf2_trunk$ src/netperf -H tardy.usa.hp.com
-t TCP_CRR -i 3,30
MIGRATED TCP Connect/Request/Response TEST from 0.0.0.0 (0.0.0.0) port 0
AF_INET to tardy.usa.hp.com () port 0 AF_INET : +/-2.500% @ 99% conf. :
demo
Local /Remote
Socket Size Request Resp. Elapsed Trans.
Send Recv Size Size Time Rate
bytes Bytes bytes bytes secs. per sec
16384 87380 1 1 10.00 2092.33
16384 87380
With MSG_FASTOPEN
raj@tardy-ubuntu-1204:~/netperf2_trunk$ src/netperf -H tardy.usa.hp.com
-t TCP_CRR -i 3,30 -- -F
MIGRATED TCP Connect/Request/Response TEST from 0.0.0.0 (0.0.0.0) port 0
AF_INET to tardy.usa.hp.com () port 0 AF_INET : +/-2.500% @ 99% conf. :
demo
!!! WARNING
!!! Desired confidence was not achieved within the specified iterations.
!!! This implies that there was variability in the test environment that
!!! must be investigated before going further.
!!! Confidence intervals: Throughput : 6.565%
!!! Local CPU util : 0.000%
!!! Remote CPU util : 0.000%
Local /Remote
Socket Size Request Resp. Elapsed Trans.
Send Recv Size Size Time Rate
bytes Bytes bytes bytes secs. per sec
16384 87380 1 1 10.00 2590.18
16384 87380
There was a ~25% increase in TCP_CRR performance, even without the
server actually accepting the magic TCP option. Is that actually
expected? Admittedly, it eliminates a connect() call, but the sequence
before was:
socket()
getsockopt(SO_SNDBUF)
getsockopt(SO_RCVBUF)
setsockopt(SO_REUSEADDR)
bind()
connect()
sendto(4, "n", 1, 0, NULL, 0) = 1
recvfrom(4, "n", 1, 0, NULL, NULL) = 1
recvfrom(4, "", 1, 0, NULL, NULL) = 0
close(4)
and with MSG_FASTOPEN only the connect() goes away. Unless connect() is
really heavy compared to what sendto(MSG_FASTOPEN) does or something
else has changed wrt behaviour.
Anyway, feel free to kick the tires on the netperf changes and let me
know of any problems you encounter.
happy benchmarking,
rick jones
^ permalink raw reply
* Re[2]: ethtool 3.5 released
From: Naoto MATSUMOTO @ 2012-08-07 1:36 UTC (permalink / raw)
To: Ben Hutchings; +Cc: netdev
In-Reply-To: <1344271283.2632.6.camel@bwh-desktop.uk.solarflarecom.com>
Hi, Ben. Thanks your reply for me.
On Mon, 6 Aug 2012 17:41:23 +0100
Ben Hutchings <bhutchings@solarflare.com> wrote:
> > Port: Twisted Pair
>
> 40G twisted-pair, eh?
We are using this one(cable).
http://www.mellanox.com/content/pages.php?pg=cables
> > PHYAD: 0
> > Transceiver: internal
> > Auto-negotiation: off
> > MDI-X: Unknown
> > Supports Wake-on: d
> > Wake-on: d
> > Current message level: 0x00000014 (20)
> > link ifdown
> > Link detected: yes
> >
> >
> > Our 40GbE NIC Firmware/Dirver status are here.
> > -----------------------------------------------------------------------
> > Mellanox ConnectX HCA Ethernet driver v1.5.8.3 (June 2012)
> > Ethernet controller: Mellanox Technologies MT27500 Family [ConnectX-3]
> > Firmware Version: 2.10.800
> > -----------------------------------------------------------------------
> >
> >
> > And We were testing 10GbE(Intel) NIC and your 40GbE NIC in our lab
> > using ethtool with added some debug code.
>
> I work for Solarflare, not Mellanox... and the patch adding 40G link
> modes came from Parav Pandit at Emulex.
>
> [...]
> > It's firmware problem I thinks. But Just Information for you ;-)
>
> Also, the 40G link mode flags were only just defined, so the driver
> probably has yet to be updated.
>
> Ben.
I agree with you. and we'll wait for the MLX_GUY works ;-)
--
SAKURA Internet Inc. / Senior Researcher
Naoto MATSUMOTO <n-matsumoto@sakura.ad.jp>
SAKURA Research Center <http://research.sakura.ad.jp/>
^ permalink raw reply
* Re[2]: [PATCH V2 09/12] net/eipoib: Add main driver functionality
From: Naoto MATSUMOTO @ 2012-08-07 1:21 UTC (permalink / raw)
To: Eric W. Biederman
Cc: Ali Ayoub, David Miller, ogerlitz, roland, netdev, sean.hefty,
erezsh, dledford
In-Reply-To: <87obmnfs4p.fsf@xmission.com>
Hi Eric, Ali
On Mon, 06 Aug 2012 17:44:06 -0700
ebiederm@xmission.com (Eric W. Biederman) wrote:
> Implementations involving bridges like macvlan and macvtap are
> performance optimizations, and the optimizations don't even apply in
> areas like 802.11, where only one mac address is supported per adapter.
We had nearly equal situation perfomance result. share for you.
-----------------------------------------------------------------------
Ethernet over EoIB using gretap with "Raid STP" performance result.
http://twitpic.com/agd1pp
How to use EoIB with gretap.
http://twitpic.com/agd4io
ifconfig ib0 10.1.1.1/24 up
ip link add eoib0 type gretap remote 10.1.1.2 local 10.1.1.1
ip link add eoib1 type gretap remote 10.1.1.3 local 10.1.1.1
ip link add type veth
ifconfig eoib0 up up
ifconfig eoib1 up up
ifconfig veth0 up up
ifconfig veth1 up up
brctl addbr br0
brctl addif br0 eoib0
brctl addif br0 eoib1
bcrtl addif br0 veth1
rstpd
rstpctl rstp br0 on
rstpctl setbridgeprio br0 40960
rstpctl setportpathcost br0 vpn1 40000
rstpctl sethello br0 1
rstpctl setmaxage br0 6
rstpctl setfdelay br0 4
brctl stp br0 on
brctl sethello br0 1
brctl setfd br0 4
brctl setmaxage br0 6
-----------------------------------------------------------------------
regards,
--
SAKURA Internet Inc. / Senior Researcher
Naoto MATSUMOTO <n-matsumoto@sakura.ad.jp>
SAKURA Research Center <http://research.sakura.ad.jp/>
^ permalink raw reply
* Re: [RFC v3 4/7] workqueue: use new hashtable implementation
From: Joe Perches @ 2012-08-07 1:19 UTC (permalink / raw)
To: Sasha Levin
Cc: torvalds, tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem,
rostedt, mingo, ebiederm, aarcange, ericvh, netdev, josh,
eric.dumazet, mathieu.desnoyers, Sasha Levin
In-Reply-To: <1344300317-23189-6-git-send-email-levinsasha928@gmail.com>
On Tue, 2012-08-07 at 02:45 +0200, Sasha Levin wrote:
> From: Sasha Levin <sasha.levin@oracle.com>
>
> Switch workqueues to use the new hashtable implementation. This reduces the amount of
> generic unrelated code in the workqueues.
Just style trivia:
> diff --git a/kernel/workqueue.c b/kernel/workqueue.c
[]
> @@ -897,8 +839,15 @@ static struct worker *__find_worker_executing_work(struct global_cwq *gcwq,
> static struct worker *find_worker_executing_work(struct global_cwq *gcwq,
> struct work_struct *work)
> {
> - return __find_worker_executing_work(gcwq, busy_worker_head(gcwq, work),
> - work);
> + struct worker *worker;
> + struct hlist_node *tmp;
> +
> + hash_for_each_possible(gcwq->busy_hash, worker, BUSY_WORKER_HASH_ORDER,
> + tmp, hentry, work)
> + if (worker->current_work == work)
> + return worker;
braces please:
hash_for_each_possible(gcwq->busy_hash, worker, BUSY_WORKER_HASH_ORDER,
tmp, hentry, work) {
if (worker->current_work == work)
return worker;
}
[]
@@ -1916,7 +1865,7 @@ static void cwq_dec_nr_in_flight(struct cpu_workqueue_struct *cwq, int color,
> * @worker: self
> * @work: work to process
> *
> - * Process @work. This function contains all the logics necessary to
> + * Process @work. This? function contains all the logics necessary to
Odd ? and the grammar also seems odd.
> * process a single work including synchronization against and
> * interaction with other workers on the same cpu, queueing and
> * flushing. As long as context requirement is met, any worker can
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply
* Re: [RFC v3 1/7] hashtable: introduce a small and naive hashtable
From: Joe Perches @ 2012-08-07 1:19 UTC (permalink / raw)
To: Sasha Levin
Cc: torvalds, tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem,
rostedt, mingo, ebiederm, aarcange, ericvh, netdev, josh,
eric.dumazet, mathieu.desnoyers
In-Reply-To: <1344300317-23189-2-git-send-email-levinsasha928@gmail.com>
On Tue, 2012-08-07 at 02:45 +0200, Sasha Levin wrote:
> This hashtable implementation is using hlist buckets to provide a simple
> hashtable to prevent it from getting reimplemented all over the kernel.
> diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
Just trivial style notes and a typo
> +/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
> +#define hash_min(val, bits) ((sizeof(val)==4)?hash_32((val), (bits)):hash_long((val), (bits)))
This is a pretty long line. It doesn't use normal kernel spacing
style and it has unnecessary parentheses.
Maybe:
#define hash_min(val, bits) \
(sizeof(val) == 4 ? hash_32(val, bits) : hash_long(val, bits))
> +
> +/**
> + * hash_init - initialize a hash table
> + * @hashtable: hashtable to be initialized
> + * @bits: bit count of hashing function
> + *
> + * Initializes a hash table with 2**bits buckets.
> + */
> +static inline void hash_init(struct hlist_head *hashtable, int bits)
> +{
> + int i;
> +
> + for (i = 0; i < HASH_SIZE(bits); i++)
> + INIT_HLIST_HEAD(hashtable + i);
> +}
Maybe use a struct hlist_head *last_hash_entry as a loop variable
{
struct hlist_head *eo_hash = hashtable + HASH_SIZE(bits);
while (hashtable < eo_hash)
INIT_HLIST_HEAD(hashtable++);
}
The compiler might generate the same code anyway...
[]
> +/**
> + * hash_for_each_possible - iterate over all possible objects for a giver key
> + * @name: hashtable to iterate
> + * @obj: the type * to use as a loop cursor for each bucke
bucket
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply
* [RFC v3 7/7] net,9p: use new hashtable implementation
From: Sasha Levin @ 2012-08-07 0:45 UTC (permalink / raw)
To: torvalds
Cc: tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem, rostedt,
mingo, ebiederm, aarcange, ericvh, netdev, josh, eric.dumazet,
mathieu.desnoyers, Sasha Levin
In-Reply-To: <1344300317-23189-1-git-send-email-levinsasha928@gmail.com>
Switch 9p error table to use the new hashtable implementation. This reduces the amount of
generic unrelated code in 9p.
Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
net/9p/error.c | 21 ++++++++++-----------
1 files changed, 10 insertions(+), 11 deletions(-)
diff --git a/net/9p/error.c b/net/9p/error.c
index 2ab2de7..f712344d 100644
--- a/net/9p/error.c
+++ b/net/9p/error.c
@@ -34,7 +34,7 @@
#include <linux/jhash.h>
#include <linux/errno.h>
#include <net/9p/9p.h>
-
+#include <linux/hashtable.h>
/**
* struct errormap - map string errors from Plan 9 to Linux numeric ids
* @name: string sent over 9P
@@ -50,8 +50,8 @@ struct errormap {
struct hlist_node list;
};
-#define ERRHASHSZ 32
-static struct hlist_head hash_errmap[ERRHASHSZ];
+#define ERR_HASH_BITS 5
+static DEFINE_HASHTABLE(hash_errmap, ERR_HASH_BITS);
/* FixMe - reduce to a reasonable size */
static struct errormap errmap[] = {
@@ -193,18 +193,17 @@ static struct errormap errmap[] = {
int p9_error_init(void)
{
struct errormap *c;
- int bucket;
+ u32 hash;
/* initialize hash table */
- for (bucket = 0; bucket < ERRHASHSZ; bucket++)
- INIT_HLIST_HEAD(&hash_errmap[bucket]);
+ hash_init(hash_errmap, ERR_HASH_BITS);
/* load initial error map into hash table */
for (c = errmap; c->name != NULL; c++) {
c->namelen = strlen(c->name);
- bucket = jhash(c->name, c->namelen, 0) % ERRHASHSZ;
+ hash = jhash(c->name, c->namelen, 0);
INIT_HLIST_NODE(&c->list);
- hlist_add_head(&c->list, &hash_errmap[bucket]);
+ hash_add(hash_errmap, ERR_HASH_BITS, &c->list, hash);
}
return 1;
@@ -223,13 +222,13 @@ int p9_errstr2errno(char *errstr, int len)
int errno;
struct hlist_node *p;
struct errormap *c;
- int bucket;
+ u32 hash;
errno = 0;
p = NULL;
c = NULL;
- bucket = jhash(errstr, len, 0) % ERRHASHSZ;
- hlist_for_each_entry(c, p, &hash_errmap[bucket], list) {
+ hash = jhash(errstr, len, 0);
+ hash_for_each_possible(hash_errmap, c, ERR_HASH_BITS, p, list, hash) {
if (c->namelen == len && !memcmp(c->name, errstr, len)) {
errno = c->val;
break;
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply related
* [RFC v3 6/7] tracepoint: use new hashtable implementation
From: Sasha Levin @ 2012-08-07 0:45 UTC (permalink / raw)
To: torvalds
Cc: tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem, rostedt,
mingo, ebiederm, aarcange, ericvh, netdev, josh, eric.dumazet,
mathieu.desnoyers, Sasha Levin
In-Reply-To: <1344300317-23189-1-git-send-email-levinsasha928@gmail.com>
Switch tracepoints to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the tracepoints.
Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
kernel/tracepoint.c | 26 ++++++++++----------------
1 files changed, 10 insertions(+), 16 deletions(-)
diff --git a/kernel/tracepoint.c b/kernel/tracepoint.c
index d96ba22..5a44949 100644
--- a/kernel/tracepoint.c
+++ b/kernel/tracepoint.c
@@ -26,6 +26,7 @@
#include <linux/slab.h>
#include <linux/sched.h>
#include <linux/static_key.h>
+#include <linux/hashtable.h>
extern struct tracepoint * const __start___tracepoints_ptrs[];
extern struct tracepoint * const __stop___tracepoints_ptrs[];
@@ -49,8 +50,7 @@ static LIST_HEAD(tracepoint_module_list);
* Protected by tracepoints_mutex.
*/
#define TRACEPOINT_HASH_BITS 6
-#define TRACEPOINT_TABLE_SIZE (1 << TRACEPOINT_HASH_BITS)
-static struct hlist_head tracepoint_table[TRACEPOINT_TABLE_SIZE];
+static DEFINE_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS);
/*
* Note about RCU :
@@ -191,16 +191,16 @@ tracepoint_entry_remove_probe(struct tracepoint_entry *entry,
*/
static struct tracepoint_entry *get_tracepoint(const char *name)
{
- struct hlist_head *head;
struct hlist_node *node;
struct tracepoint_entry *e;
u32 hash = jhash(name, strlen(name), 0);
- head = &tracepoint_table[hash & (TRACEPOINT_TABLE_SIZE - 1)];
- hlist_for_each_entry(e, node, head, hlist) {
+ hash_for_each_possible(tracepoint_table, e, TRACEPOINT_HASH_BITS,
+ node, hlist, hash) {
if (!strcmp(name, e->name))
return e;
}
+
return NULL;
}
@@ -210,19 +210,13 @@ static struct tracepoint_entry *get_tracepoint(const char *name)
*/
static struct tracepoint_entry *add_tracepoint(const char *name)
{
- struct hlist_head *head;
- struct hlist_node *node;
struct tracepoint_entry *e;
size_t name_len = strlen(name) + 1;
u32 hash = jhash(name, name_len-1, 0);
- head = &tracepoint_table[hash & (TRACEPOINT_TABLE_SIZE - 1)];
- hlist_for_each_entry(e, node, head, hlist) {
- if (!strcmp(name, e->name)) {
- printk(KERN_NOTICE
- "tracepoint %s busy\n", name);
- return ERR_PTR(-EEXIST); /* Already there */
- }
+ if (get_tracepoint(name)) {
+ printk(KERN_NOTICE "tracepoint %s busy\n", name);
+ return ERR_PTR(-EEXIST); /* Already there */
}
/*
* Using kmalloc here to allocate a variable length element. Could
@@ -234,7 +228,7 @@ static struct tracepoint_entry *add_tracepoint(const char *name)
memcpy(&e->name[0], name, name_len);
e->funcs = NULL;
e->refcount = 0;
- hlist_add_head(&e->hlist, head);
+ hash_add(tracepoint_table, TRACEPOINT_HASH_BITS, &e->hlist, hash);
return e;
}
@@ -244,7 +238,7 @@ static struct tracepoint_entry *add_tracepoint(const char *name)
*/
static inline void remove_tracepoint(struct tracepoint_entry *e)
{
- hlist_del(&e->hlist);
+ hash_del(&e->hlist);
kfree(e);
}
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply related
* [RFC v3 5/7] mm/huge_memory: use new hashtable implementation
From: Sasha Levin @ 2012-08-07 0:45 UTC (permalink / raw)
To: torvalds
Cc: tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem, rostedt,
mingo, ebiederm, aarcange, ericvh, netdev, josh, eric.dumazet,
mathieu.desnoyers, Sasha Levin
In-Reply-To: <1344300317-23189-1-git-send-email-levinsasha928@gmail.com>
Switch hugemem to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the hugemem.
This also removes the dymanic allocation of the hash table. The size of the table is
constant so there's no point in paying the price of an extra dereference when accessing
it.
Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
mm/huge_memory.c | 56 +++++++++++++----------------------------------------
1 files changed, 14 insertions(+), 42 deletions(-)
diff --git a/mm/huge_memory.c b/mm/huge_memory.c
index 57c4b93..e4c752d 100644
--- a/mm/huge_memory.c
+++ b/mm/huge_memory.c
@@ -17,6 +17,7 @@
#include <linux/khugepaged.h>
#include <linux/freezer.h>
#include <linux/mman.h>
+#include <linux/hashtable.h>
#include <asm/tlb.h>
#include <asm/pgalloc.h>
#include "internal.h"
@@ -57,12 +58,12 @@ static DECLARE_WAIT_QUEUE_HEAD(khugepaged_wait);
static unsigned int khugepaged_max_ptes_none __read_mostly = HPAGE_PMD_NR-1;
static int khugepaged(void *none);
-static int mm_slots_hash_init(void);
static int khugepaged_slab_init(void);
static void khugepaged_slab_free(void);
-#define MM_SLOTS_HASH_HEADS 1024
-static struct hlist_head *mm_slots_hash __read_mostly;
+#define MM_SLOTS_HASH_BITS 10
+static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS);
+
static struct kmem_cache *mm_slot_cache __read_mostly;
/**
@@ -140,7 +141,7 @@ static int start_khugepaged(void)
int err = 0;
if (khugepaged_enabled()) {
int wakeup;
- if (unlikely(!mm_slot_cache || !mm_slots_hash)) {
+ if (unlikely(!mm_slot_cache)) {
err = -ENOMEM;
goto out;
}
@@ -554,12 +555,6 @@ static int __init hugepage_init(void)
if (err)
goto out;
- err = mm_slots_hash_init();
- if (err) {
- khugepaged_slab_free();
- goto out;
- }
-
/*
* By default disable transparent hugepages on smaller systems,
* where the extra memory used could hurt more than TLB overhead
@@ -1562,47 +1557,24 @@ static inline void free_mm_slot(struct mm_slot *mm_slot)
kmem_cache_free(mm_slot_cache, mm_slot);
}
-static int __init mm_slots_hash_init(void)
-{
- mm_slots_hash = kzalloc(MM_SLOTS_HASH_HEADS * sizeof(struct hlist_head),
- GFP_KERNEL);
- if (!mm_slots_hash)
- return -ENOMEM;
- return 0;
-}
-
-#if 0
-static void __init mm_slots_hash_free(void)
-{
- kfree(mm_slots_hash);
- mm_slots_hash = NULL;
-}
-#endif
-
static struct mm_slot *get_mm_slot(struct mm_struct *mm)
{
- struct mm_slot *mm_slot;
- struct hlist_head *bucket;
+ struct mm_slot *slot;
struct hlist_node *node;
- bucket = &mm_slots_hash[((unsigned long)mm / sizeof(struct mm_struct))
- % MM_SLOTS_HASH_HEADS];
- hlist_for_each_entry(mm_slot, node, bucket, hash) {
- if (mm == mm_slot->mm)
- return mm_slot;
- }
+ hash_for_each_possible(mm_slots_hash, slot, MM_SLOTS_HASH_BITS, node,
+ hash, (unsigned long) mm)
+ if (slot->mm == mm)
+ return slot;
+
return NULL;
}
static void insert_to_mm_slots_hash(struct mm_struct *mm,
struct mm_slot *mm_slot)
{
- struct hlist_head *bucket;
-
- bucket = &mm_slots_hash[((unsigned long)mm / sizeof(struct mm_struct))
- % MM_SLOTS_HASH_HEADS];
mm_slot->mm = mm;
- hlist_add_head(&mm_slot->hash, bucket);
+ hash_add(mm_slots_hash, MM_SLOTS_HASH_BITS, &mm_slot->hash, (long)mm);
}
static inline int khugepaged_test_exit(struct mm_struct *mm)
@@ -1675,7 +1647,7 @@ void __khugepaged_exit(struct mm_struct *mm)
spin_lock(&khugepaged_mm_lock);
mm_slot = get_mm_slot(mm);
if (mm_slot && khugepaged_scan.mm_slot != mm_slot) {
- hlist_del(&mm_slot->hash);
+ hash_del(&mm_slot->hash);
list_del(&mm_slot->mm_node);
free = 1;
}
@@ -2089,7 +2061,7 @@ static void collect_mm_slot(struct mm_slot *mm_slot)
if (khugepaged_test_exit(mm)) {
/* free mm_slot */
- hlist_del(&mm_slot->hash);
+ hash_del(&mm_slot->hash);
list_del(&mm_slot->mm_node);
/*
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply related
* [RFC v3 4/7] workqueue: use new hashtable implementation
From: Sasha Levin @ 2012-08-07 0:45 UTC (permalink / raw)
To: torvalds
Cc: tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem, rostedt,
mingo, ebiederm, aarcange, ericvh, netdev, josh, eric.dumazet,
mathieu.desnoyers, Sasha Levin
In-Reply-To: <1344300317-23189-1-git-send-email-levinsasha928@gmail.com>
From: Sasha Levin <sasha.levin@oracle.com>
Switch workqueues to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the workqueues.
Signed-off-by: Sasha Levin <sasha.levin@oracle.com>
---
kernel/workqueue.c | 91 +++++++++++-----------------------------------------
1 files changed, 19 insertions(+), 72 deletions(-)
diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index 692d976..edc7fd0 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -41,6 +41,7 @@
#include <linux/debug_locks.h>
#include <linux/lockdep.h>
#include <linux/idr.h>
+#include <linux/hashtable.h>
#include "workqueue_sched.h"
@@ -82,8 +83,6 @@ enum {
NR_WORKER_POOLS = 2, /* # worker pools per gcwq */
BUSY_WORKER_HASH_ORDER = 6, /* 64 pointers */
- BUSY_WORKER_HASH_SIZE = 1 << BUSY_WORKER_HASH_ORDER,
- BUSY_WORKER_HASH_MASK = BUSY_WORKER_HASH_SIZE - 1,
MAX_IDLE_WORKERS_RATIO = 4, /* 1/4 of busy can be idle */
IDLE_WORKER_TIMEOUT = 300 * HZ, /* keep idle ones for 5 mins */
@@ -180,7 +179,7 @@ struct global_cwq {
unsigned int flags; /* L: GCWQ_* flags */
/* workers are chained either in busy_hash or pool idle_list */
- struct hlist_head busy_hash[BUSY_WORKER_HASH_SIZE];
+ DEFINE_HASHTABLE(busy_hash, BUSY_WORKER_HASH_ORDER);
/* L: hash of busy workers */
struct worker_pool pools[2]; /* normal and highpri pools */
@@ -288,8 +287,8 @@ EXPORT_SYMBOL_GPL(system_nrt_freezable_wq);
(pool) < &(gcwq)->pools[NR_WORKER_POOLS]; (pool)++)
#define for_each_busy_worker(worker, i, pos, gcwq) \
- for (i = 0; i < BUSY_WORKER_HASH_SIZE; i++) \
- hlist_for_each_entry(worker, pos, &gcwq->busy_hash[i], hentry)
+ hash_for_each(gcwq->busy_hash, BUSY_WORKER_HASH_ORDER, i, pos, \
+ worker, hentry)
static inline int __next_gcwq_cpu(int cpu, const struct cpumask *mask,
unsigned int sw)
@@ -822,63 +821,6 @@ static inline void worker_clr_flags(struct worker *worker, unsigned int flags)
}
/**
- * busy_worker_head - return the busy hash head for a work
- * @gcwq: gcwq of interest
- * @work: work to be hashed
- *
- * Return hash head of @gcwq for @work.
- *
- * CONTEXT:
- * spin_lock_irq(gcwq->lock).
- *
- * RETURNS:
- * Pointer to the hash head.
- */
-static struct hlist_head *busy_worker_head(struct global_cwq *gcwq,
- struct work_struct *work)
-{
- const int base_shift = ilog2(sizeof(struct work_struct));
- unsigned long v = (unsigned long)work;
-
- /* simple shift and fold hash, do we need something better? */
- v >>= base_shift;
- v += v >> BUSY_WORKER_HASH_ORDER;
- v &= BUSY_WORKER_HASH_MASK;
-
- return &gcwq->busy_hash[v];
-}
-
-/**
- * __find_worker_executing_work - find worker which is executing a work
- * @gcwq: gcwq of interest
- * @bwh: hash head as returned by busy_worker_head()
- * @work: work to find worker for
- *
- * Find a worker which is executing @work on @gcwq. @bwh should be
- * the hash head obtained by calling busy_worker_head() with the same
- * work.
- *
- * CONTEXT:
- * spin_lock_irq(gcwq->lock).
- *
- * RETURNS:
- * Pointer to worker which is executing @work if found, NULL
- * otherwise.
- */
-static struct worker *__find_worker_executing_work(struct global_cwq *gcwq,
- struct hlist_head *bwh,
- struct work_struct *work)
-{
- struct worker *worker;
- struct hlist_node *tmp;
-
- hlist_for_each_entry(worker, tmp, bwh, hentry)
- if (worker->current_work == work)
- return worker;
- return NULL;
-}
-
-/**
* find_worker_executing_work - find worker which is executing a work
* @gcwq: gcwq of interest
* @work: work to find worker for
@@ -897,8 +839,15 @@ static struct worker *__find_worker_executing_work(struct global_cwq *gcwq,
static struct worker *find_worker_executing_work(struct global_cwq *gcwq,
struct work_struct *work)
{
- return __find_worker_executing_work(gcwq, busy_worker_head(gcwq, work),
- work);
+ struct worker *worker;
+ struct hlist_node *tmp;
+
+ hash_for_each_possible(gcwq->busy_hash, worker, BUSY_WORKER_HASH_ORDER,
+ tmp, hentry, work)
+ if (worker->current_work == work)
+ return worker;
+
+ return NULL;
}
/**
@@ -1916,7 +1865,7 @@ static void cwq_dec_nr_in_flight(struct cpu_workqueue_struct *cwq, int color,
* @worker: self
* @work: work to process
*
- * Process @work. This function contains all the logics necessary to
+ * Process @work. This? function contains all the logics necessary to
* process a single work including synchronization against and
* interaction with other workers on the same cpu, queueing and
* flushing. As long as context requirement is met, any worker can
@@ -1932,7 +1881,6 @@ __acquires(&gcwq->lock)
struct cpu_workqueue_struct *cwq = get_work_cwq(work);
struct worker_pool *pool = worker->pool;
struct global_cwq *gcwq = pool->gcwq;
- struct hlist_head *bwh = busy_worker_head(gcwq, work);
bool cpu_intensive = cwq->wq->flags & WQ_CPU_INTENSIVE;
work_func_t f = work->func;
int work_color;
@@ -1964,7 +1912,7 @@ __acquires(&gcwq->lock)
* already processing the work. If so, defer the work to the
* currently executing one.
*/
- collision = __find_worker_executing_work(gcwq, bwh, work);
+ collision = find_worker_executing_work(gcwq, work);
if (unlikely(collision)) {
move_linked_works(work, &collision->scheduled, NULL);
return;
@@ -1972,7 +1920,8 @@ __acquires(&gcwq->lock)
/* claim and process */
debug_work_deactivate(work);
- hlist_add_head(&worker->hentry, bwh);
+ hash_add(gcwq->busy_hash, BUSY_WORKER_HASH_ORDER, &worker->hentry,
+ (unsigned long)worker);
worker->current_work = work;
worker->current_cwq = cwq;
work_color = get_work_color(work);
@@ -2027,7 +1976,7 @@ __acquires(&gcwq->lock)
worker_clr_flags(worker, WORKER_CPU_INTENSIVE);
/* we're done with it, release */
- hlist_del_init(&worker->hentry);
+ hash_del(&worker->hentry);
worker->current_work = NULL;
worker->current_cwq = NULL;
cwq_dec_nr_in_flight(cwq, work_color, false);
@@ -3690,7 +3639,6 @@ out_unlock:
static int __init init_workqueues(void)
{
unsigned int cpu;
- int i;
cpu_notifier(workqueue_cpu_up_callback, CPU_PRI_WORKQUEUE_UP);
cpu_notifier(workqueue_cpu_down_callback, CPU_PRI_WORKQUEUE_DOWN);
@@ -3704,8 +3652,7 @@ static int __init init_workqueues(void)
gcwq->cpu = cpu;
gcwq->flags |= GCWQ_DISASSOCIATED;
- for (i = 0; i < BUSY_WORKER_HASH_SIZE; i++)
- INIT_HLIST_HEAD(&gcwq->busy_hash[i]);
+ hash_init(gcwq->busy_hash, BUSY_WORKER_HASH_ORDER);
for_each_worker_pool(pool, gcwq) {
pool->gcwq = gcwq;
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply related
* [RFC v3 4/7] workqueue: use new hashtable implementation
From: Sasha Levin @ 2012-08-07 0:45 UTC (permalink / raw)
To: torvalds
Cc: tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem, rostedt,
mingo, ebiederm, aarcange, ericvh, netdev, josh, eric.dumazet,
mathieu.desnoyers, Sasha Levin
In-Reply-To: <1344300317-23189-1-git-send-email-levinsasha928@gmail.com>
Switch workqueues to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the workqueues.
Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
kernel/workqueue.c | 89 ++++++++++-----------------------------------------
1 files changed, 18 insertions(+), 71 deletions(-)
diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index 692d976..548fa87 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -41,6 +41,7 @@
#include <linux/debug_locks.h>
#include <linux/lockdep.h>
#include <linux/idr.h>
+#include <linux/hashtable.h>
#include "workqueue_sched.h"
@@ -82,8 +83,6 @@ enum {
NR_WORKER_POOLS = 2, /* # worker pools per gcwq */
BUSY_WORKER_HASH_ORDER = 6, /* 64 pointers */
- BUSY_WORKER_HASH_SIZE = 1 << BUSY_WORKER_HASH_ORDER,
- BUSY_WORKER_HASH_MASK = BUSY_WORKER_HASH_SIZE - 1,
MAX_IDLE_WORKERS_RATIO = 4, /* 1/4 of busy can be idle */
IDLE_WORKER_TIMEOUT = 300 * HZ, /* keep idle ones for 5 mins */
@@ -180,7 +179,7 @@ struct global_cwq {
unsigned int flags; /* L: GCWQ_* flags */
/* workers are chained either in busy_hash or pool idle_list */
- struct hlist_head busy_hash[BUSY_WORKER_HASH_SIZE];
+ DEFINE_HASHTABLE(busy_hash, BUSY_WORKER_HASH_ORDER);
/* L: hash of busy workers */
struct worker_pool pools[2]; /* normal and highpri pools */
@@ -288,8 +287,8 @@ EXPORT_SYMBOL_GPL(system_nrt_freezable_wq);
(pool) < &(gcwq)->pools[NR_WORKER_POOLS]; (pool)++)
#define for_each_busy_worker(worker, i, pos, gcwq) \
- for (i = 0; i < BUSY_WORKER_HASH_SIZE; i++) \
- hlist_for_each_entry(worker, pos, &gcwq->busy_hash[i], hentry)
+ hash_for_each(gcwq->busy_hash, BUSY_WORKER_HASH_ORDER, i, pos, \
+ worker, hentry)
static inline int __next_gcwq_cpu(int cpu, const struct cpumask *mask,
unsigned int sw)
@@ -822,63 +821,6 @@ static inline void worker_clr_flags(struct worker *worker, unsigned int flags)
}
/**
- * busy_worker_head - return the busy hash head for a work
- * @gcwq: gcwq of interest
- * @work: work to be hashed
- *
- * Return hash head of @gcwq for @work.
- *
- * CONTEXT:
- * spin_lock_irq(gcwq->lock).
- *
- * RETURNS:
- * Pointer to the hash head.
- */
-static struct hlist_head *busy_worker_head(struct global_cwq *gcwq,
- struct work_struct *work)
-{
- const int base_shift = ilog2(sizeof(struct work_struct));
- unsigned long v = (unsigned long)work;
-
- /* simple shift and fold hash, do we need something better? */
- v >>= base_shift;
- v += v >> BUSY_WORKER_HASH_ORDER;
- v &= BUSY_WORKER_HASH_MASK;
-
- return &gcwq->busy_hash[v];
-}
-
-/**
- * __find_worker_executing_work - find worker which is executing a work
- * @gcwq: gcwq of interest
- * @bwh: hash head as returned by busy_worker_head()
- * @work: work to find worker for
- *
- * Find a worker which is executing @work on @gcwq. @bwh should be
- * the hash head obtained by calling busy_worker_head() with the same
- * work.
- *
- * CONTEXT:
- * spin_lock_irq(gcwq->lock).
- *
- * RETURNS:
- * Pointer to worker which is executing @work if found, NULL
- * otherwise.
- */
-static struct worker *__find_worker_executing_work(struct global_cwq *gcwq,
- struct hlist_head *bwh,
- struct work_struct *work)
-{
- struct worker *worker;
- struct hlist_node *tmp;
-
- hlist_for_each_entry(worker, tmp, bwh, hentry)
- if (worker->current_work == work)
- return worker;
- return NULL;
-}
-
-/**
* find_worker_executing_work - find worker which is executing a work
* @gcwq: gcwq of interest
* @work: work to find worker for
@@ -897,8 +839,15 @@ static struct worker *__find_worker_executing_work(struct global_cwq *gcwq,
static struct worker *find_worker_executing_work(struct global_cwq *gcwq,
struct work_struct *work)
{
- return __find_worker_executing_work(gcwq, busy_worker_head(gcwq, work),
- work);
+ struct worker *worker;
+ struct hlist_node *tmp;
+
+ hash_for_each_possible(gcwq->busy_hash, worker, BUSY_WORKER_HASH_ORDER,
+ tmp, hentry, (unsigned long)work)
+ if (worker->current_work == work)
+ return worker;
+
+ return NULL;
}
/**
@@ -1932,7 +1881,6 @@ __acquires(&gcwq->lock)
struct cpu_workqueue_struct *cwq = get_work_cwq(work);
struct worker_pool *pool = worker->pool;
struct global_cwq *gcwq = pool->gcwq;
- struct hlist_head *bwh = busy_worker_head(gcwq, work);
bool cpu_intensive = cwq->wq->flags & WQ_CPU_INTENSIVE;
work_func_t f = work->func;
int work_color;
@@ -1964,7 +1912,7 @@ __acquires(&gcwq->lock)
* already processing the work. If so, defer the work to the
* currently executing one.
*/
- collision = __find_worker_executing_work(gcwq, bwh, work);
+ collision = find_worker_executing_work(gcwq, work);
if (unlikely(collision)) {
move_linked_works(work, &collision->scheduled, NULL);
return;
@@ -1972,7 +1920,8 @@ __acquires(&gcwq->lock)
/* claim and process */
debug_work_deactivate(work);
- hlist_add_head(&worker->hentry, bwh);
+ hash_add(gcwq->busy_hash, BUSY_WORKER_HASH_ORDER, &worker->hentry,
+ (unsigned long)worker);
worker->current_work = work;
worker->current_cwq = cwq;
work_color = get_work_color(work);
@@ -2027,7 +1976,7 @@ __acquires(&gcwq->lock)
worker_clr_flags(worker, WORKER_CPU_INTENSIVE);
/* we're done with it, release */
- hlist_del_init(&worker->hentry);
+ hash_del(&worker->hentry);
worker->current_work = NULL;
worker->current_cwq = NULL;
cwq_dec_nr_in_flight(cwq, work_color, false);
@@ -3690,7 +3639,6 @@ out_unlock:
static int __init init_workqueues(void)
{
unsigned int cpu;
- int i;
cpu_notifier(workqueue_cpu_up_callback, CPU_PRI_WORKQUEUE_UP);
cpu_notifier(workqueue_cpu_down_callback, CPU_PRI_WORKQUEUE_DOWN);
@@ -3704,8 +3652,7 @@ static int __init init_workqueues(void)
gcwq->cpu = cpu;
gcwq->flags |= GCWQ_DISASSOCIATED;
- for (i = 0; i < BUSY_WORKER_HASH_SIZE; i++)
- INIT_HLIST_HEAD(&gcwq->busy_hash[i]);
+ hash_init(gcwq->busy_hash, BUSY_WORKER_HASH_ORDER);
for_each_worker_pool(pool, gcwq) {
pool->gcwq = gcwq;
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply related
* [RFC v3 3/7] mm,ksm: use new hashtable implementation
From: Sasha Levin @ 2012-08-07 0:45 UTC (permalink / raw)
To: torvalds
Cc: tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem, rostedt,
mingo, ebiederm, aarcange, ericvh, netdev, josh, eric.dumazet,
mathieu.desnoyers, Sasha Levin
In-Reply-To: <1344300317-23189-1-git-send-email-levinsasha928@gmail.com>
Switch ksm to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the ksm module.
Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
mm/ksm.c | 31 +++++++++++++------------------
1 files changed, 13 insertions(+), 18 deletions(-)
diff --git a/mm/ksm.c b/mm/ksm.c
index 47c8853..96d5f91 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -33,7 +33,7 @@
#include <linux/mmu_notifier.h>
#include <linux/swap.h>
#include <linux/ksm.h>
-#include <linux/hash.h>
+#include <linux/hashtable.h>
#include <linux/freezer.h>
#include <linux/oom.h>
@@ -156,9 +156,8 @@ struct rmap_item {
static struct rb_root root_stable_tree = RB_ROOT;
static struct rb_root root_unstable_tree = RB_ROOT;
-#define MM_SLOTS_HASH_SHIFT 10
-#define MM_SLOTS_HASH_HEADS (1 << MM_SLOTS_HASH_SHIFT)
-static struct hlist_head mm_slots_hash[MM_SLOTS_HASH_HEADS];
+#define MM_SLOTS_HASH_BITS 10
+static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS);
static struct mm_slot ksm_mm_head = {
.mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list),
@@ -275,26 +274,22 @@ static inline void free_mm_slot(struct mm_slot *mm_slot)
static struct mm_slot *get_mm_slot(struct mm_struct *mm)
{
- struct mm_slot *mm_slot;
- struct hlist_head *bucket;
struct hlist_node *node;
+ struct mm_slot *slot;
+
+ hash_for_each_possible(mm_slots_hash, slot, MM_SLOTS_HASH_BITS,
+ node, link, (unsigned long)mm)
+ if (slot->mm == mm)
+ return slot;
- bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)];
- hlist_for_each_entry(mm_slot, node, bucket, link) {
- if (mm == mm_slot->mm)
- return mm_slot;
- }
return NULL;
}
static void insert_to_mm_slots_hash(struct mm_struct *mm,
struct mm_slot *mm_slot)
{
- struct hlist_head *bucket;
-
- bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)];
mm_slot->mm = mm;
- hlist_add_head(&mm_slot->link, bucket);
+ hash_add(mm_slots_hash, MM_SLOTS_HASH_BITS, &mm_slot->link, (long)mm);
}
static inline int in_stable_tree(struct rmap_item *rmap_item)
@@ -647,7 +642,7 @@ static int unmerge_and_remove_all_rmap_items(void)
ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next,
struct mm_slot, mm_list);
if (ksm_test_exit(mm)) {
- hlist_del(&mm_slot->link);
+ hash_del(&mm_slot->link);
list_del(&mm_slot->mm_list);
spin_unlock(&ksm_mmlist_lock);
@@ -1385,7 +1380,7 @@ next_mm:
* or when all VM_MERGEABLE areas have been unmapped (and
* mmap_sem then protects against race with MADV_MERGEABLE).
*/
- hlist_del(&slot->link);
+ hash_del(&slot->link);
list_del(&slot->mm_list);
spin_unlock(&ksm_mmlist_lock);
@@ -1548,7 +1543,7 @@ void __ksm_exit(struct mm_struct *mm)
mm_slot = get_mm_slot(mm);
if (mm_slot && ksm_scan.mm_slot != mm_slot) {
if (!mm_slot->rmap_list) {
- hlist_del(&mm_slot->link);
+ hash_del(&mm_slot->link);
list_del(&mm_slot->mm_list);
easy_to_free = 1;
} else {
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply related
* [RFC v3 2/7] user_ns: use new hashtable implementation
From: Sasha Levin @ 2012-08-07 0:45 UTC (permalink / raw)
To: torvalds
Cc: tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem, rostedt,
mingo, ebiederm, aarcange, ericvh, netdev, josh, eric.dumazet,
mathieu.desnoyers, Sasha Levin
In-Reply-To: <1344300317-23189-1-git-send-email-levinsasha928@gmail.com>
Switch user_ns to use the new hashtable implementation. This reduces the amount of
generic unrelated code in user_ns.
Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
kernel/user.c | 35 +++++++++++++++--------------------
1 files changed, 15 insertions(+), 20 deletions(-)
diff --git a/kernel/user.c b/kernel/user.c
index b815fef..400a23cf 100644
--- a/kernel/user.c
+++ b/kernel/user.c
@@ -16,6 +16,7 @@
#include <linux/interrupt.h>
#include <linux/export.h>
#include <linux/user_namespace.h>
+#include <linux/hashtable.h>
/*
* userns count is 1 for root user, 1 for init_uts_ns,
@@ -52,13 +53,9 @@ EXPORT_SYMBOL_GPL(init_user_ns);
*/
#define UIDHASH_BITS (CONFIG_BASE_SMALL ? 3 : 7)
-#define UIDHASH_SZ (1 << UIDHASH_BITS)
-#define UIDHASH_MASK (UIDHASH_SZ - 1)
-#define __uidhashfn(uid) (((uid >> UIDHASH_BITS) + uid) & UIDHASH_MASK)
-#define uidhashentry(uid) (uidhash_table + __uidhashfn((__kuid_val(uid))))
static struct kmem_cache *uid_cachep;
-struct hlist_head uidhash_table[UIDHASH_SZ];
+static DEFINE_HASHTABLE(uidhash_table, UIDHASH_BITS)
/*
* The uidhash_lock is mostly taken from process context, but it is
@@ -84,22 +81,24 @@ struct user_struct root_user = {
/*
* These routines must be called with the uidhash spinlock held!
*/
-static void uid_hash_insert(struct user_struct *up, struct hlist_head *hashent)
+static void uid_hash_insert(struct user_struct *up)
{
- hlist_add_head(&up->uidhash_node, hashent);
+ hash_add(uidhash_table, UIDHASH_BITS, &up->uidhash_node,
+ __kuid_val(up->uid));
}
static void uid_hash_remove(struct user_struct *up)
{
- hlist_del_init(&up->uidhash_node);
+ hash_del(&up->uidhash_node);
}
-static struct user_struct *uid_hash_find(kuid_t uid, struct hlist_head *hashent)
+static struct user_struct *uid_hash_find(kuid_t uid)
{
struct user_struct *user;
struct hlist_node *h;
- hlist_for_each_entry(user, h, hashent, uidhash_node) {
+ hash_for_each_possible(uidhash_table, user, UIDHASH_BITS, h, uidhash_node,
+ __kuid_val(uid)) {
if (uid_eq(user->uid, uid)) {
atomic_inc(&user->__count);
return user;
@@ -135,7 +134,7 @@ struct user_struct *find_user(kuid_t uid)
unsigned long flags;
spin_lock_irqsave(&uidhash_lock, flags);
- ret = uid_hash_find(uid, uidhashentry(uid));
+ ret = uid_hash_find(uid);
spin_unlock_irqrestore(&uidhash_lock, flags);
return ret;
}
@@ -156,11 +155,10 @@ void free_uid(struct user_struct *up)
struct user_struct *alloc_uid(kuid_t uid)
{
- struct hlist_head *hashent = uidhashentry(uid);
struct user_struct *up, *new;
spin_lock_irq(&uidhash_lock);
- up = uid_hash_find(uid, hashent);
+ up = uid_hash_find(uid);
spin_unlock_irq(&uidhash_lock);
if (!up) {
@@ -176,13 +174,13 @@ struct user_struct *alloc_uid(kuid_t uid)
* on adding the same user already..
*/
spin_lock_irq(&uidhash_lock);
- up = uid_hash_find(uid, hashent);
+ up = uid_hash_find(uid);
if (up) {
key_put(new->uid_keyring);
key_put(new->session_keyring);
kmem_cache_free(uid_cachep, new);
} else {
- uid_hash_insert(new, hashent);
+ uid_hash_insert(new);
up = new;
}
spin_unlock_irq(&uidhash_lock);
@@ -196,17 +194,14 @@ out_unlock:
static int __init uid_cache_init(void)
{
- int n;
-
uid_cachep = kmem_cache_create("uid_cache", sizeof(struct user_struct),
0, SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
- for(n = 0; n < UIDHASH_SZ; ++n)
- INIT_HLIST_HEAD(uidhash_table + n);
+ hash_init(uidhash_table, UIDHASH_BITS);
/* Insert the root user immediately (init already runs as root) */
spin_lock_irq(&uidhash_lock);
- uid_hash_insert(&root_user, uidhashentry(GLOBAL_ROOT_UID));
+ uid_hash_insert(&root_user);
spin_unlock_irq(&uidhash_lock);
return 0;
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply related
* [RFC v3 1/7] hashtable: introduce a small and naive hashtable
From: Sasha Levin @ 2012-08-07 0:45 UTC (permalink / raw)
To: torvalds
Cc: tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem, rostedt,
mingo, ebiederm, aarcange, ericvh, netdev, josh, eric.dumazet,
mathieu.desnoyers, Sasha Levin
In-Reply-To: <1344300317-23189-1-git-send-email-levinsasha928@gmail.com>
This hashtable implementation is using hlist buckets to provide a simple
hashtable to prevent it from getting reimplemented all over the kernel.
Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
include/linux/hashtable.h | 82 +++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 82 insertions(+), 0 deletions(-)
create mode 100644 include/linux/hashtable.h
diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
new file mode 100644
index 0000000..394652b
--- /dev/null
+++ b/include/linux/hashtable.h
@@ -0,0 +1,82 @@
+/*
+ * Hash table implementation
+ * (C) 2012 Sasha Levin <levinsasha928@gmail.com>
+ */
+
+#ifndef _LINUX_HASHTABLE_H
+#define _LINUX_HASHTABLE_H
+
+#include <linux/list.h>
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/hash.h>
+
+#define DEFINE_HASHTABLE(name, bits) \
+ struct hlist_head name[HASH_SIZE(bits)];
+
+#define HASH_SIZE(bits) (1 << (bits))
+
+/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
+#define hash_min(val, bits) ((sizeof(val)==4)?hash_32((val), (bits)):hash_long((val), (bits)))
+
+/**
+ * hash_init - initialize a hash table
+ * @hashtable: hashtable to be initialized
+ * @bits: bit count of hashing function
+ *
+ * Initializes a hash table with 2**bits buckets.
+ */
+static inline void hash_init(struct hlist_head *hashtable, int bits)
+{
+ int i;
+
+ for (i = 0; i < HASH_SIZE(bits); i++)
+ INIT_HLIST_HEAD(hashtable + i);
+}
+
+/**
+ * hash_add - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the &struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add(hashtable, bits, node, key) \
+ hlist_add_head(node, &hashtable[hash_min(key, bits)]);
+
+/**
+ * hash_del - remove an object from a hashtable
+ * @node: &struct hlist_node of the object to remove
+ */
+static inline void hash_del(struct hlist_node *node)
+{
+ hlist_del_init(node);
+}
+
+/**
+ * hash_for_each - iterate over a hashtable
+ * @name: hashtable to iterate
+ * @bits: bit count of hashing function of the hashtable
+ * @bkt: integer to use as bucket loop cursor
+ * @node: the &struct list_head to use as a loop cursor for each bucket
+ * @obj: the type * to use as a loop cursor for each bucket
+ * @member: the name of the hlist_node within the struct
+ */
+#define hash_for_each(name, bits, bkt, node, obj, member) \
+ for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
+ hlist_for_each_entry(obj, node, &name[i], member)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects for a giver key
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each bucke
+ * @bits: bit count of hashing function of the hashtable
+ * @node: the &struct list_head to use as a loop cursor for each bucket
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible(name, obj, bits, node, member, key) \
+ hlist_for_each_entry(obj, node, \
+ &name[hash_min(key, bits)], member)
+
+#endif
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply related
* [RFC v3 0/7] generic hashtable implementation
From: Sasha Levin @ 2012-08-07 0:45 UTC (permalink / raw)
To: torvalds
Cc: tj, akpm, linux-kernel, linux-mm, paul.gortmaker, davem, rostedt,
mingo, ebiederm, aarcange, ericvh, netdev, josh, eric.dumazet,
mathieu.desnoyers, Sasha Levin
There are quite a few places in the kernel which implement a hashtable
in a very similar way. Instead of having implementations of a hashtable
all over the kernel, we can re-use the code.
This patch series introduces a very simple hashtable implementation, and
modifies three (random) modules to use it. I've limited it to 3 only
so that it would be easy to review and modify, and to show that even
at this number we already eliminate a big amount of duplicated code.
If this basic hashtable looks ok, future code will include:
- RCU support
- Self locking (list_bl?)
- Converting more code to use the hashtable
Changes in V3:
- Address review comments by Tejun Heo, Josh Triplett, Eric Beiderman,
Mathieu Desnoyers, Eric Dumazet and Linus Torvalds.
- Removed hash_get due to being too Gandalf.
- Rewrote the user namespaces hash implementation.
- Hashtable went back to being a simple array of buckets, but without any
of the macro tricks to get the size automatically.
- Optimize hasing if key is 32 bits long.
Changes in V2:
- Address review comments by Tejun Heo, Josh Triplett and Eric Beiderman (Thanks all!).
- Rebase on top of latest master.
- Convert more places to use the hashtable. Hopefully it will trigger more reviews by
touching more subsystems.
Sasha Levin (7):
hashtable: introduce a small and naive hashtable
user_ns: use new hashtable implementation
mm,ksm: use new hashtable implementation
workqueue: use new hashtable implementation
mm/huge_memory: use new hashtable implementation
tracepoint: use new hashtable implementation
net,9p: use new hashtable implementation
include/linux/hashtable.h | 82 +++++++++++++++++++++++++++++++++++++++++
kernel/tracepoint.c | 26 +++++--------
kernel/user.c | 35 ++++++++----------
kernel/workqueue.c | 89 +++++++++------------------------------------
mm/huge_memory.c | 56 +++++++---------------------
mm/ksm.c | 31 +++++++---------
net/9p/error.c | 21 +++++------
7 files changed, 162 insertions(+), 178 deletions(-)
create mode 100644 include/linux/hashtable.h
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply
* Re: [PATCH V2 09/12] net/eipoib: Add main driver functionality
From: Eric W. Biederman @ 2012-08-07 0:44 UTC (permalink / raw)
To: Ali Ayoub
Cc: David Miller, ogerlitz, roland, netdev, sean.hefty, erezsh,
dledford
In-Reply-To: <50205DE0.7080706@mellanox.com>
Ali Ayoub <ali@mellanox.com> writes:
> Among other things, the main benefit we're targeting is to allow IPoE
> traffic within the VM to go through the (Ethernet) vBridge down to the
> eIPoIB PIF, and eventually to IPoIB and to the IB network.
That works today without code changes. It is called routing.
> In Para virtualized environment, the VM emulator sends/receives packets
> with Ethernet header, and the vBridge also performs L2 switching based
> on the Ethernet header, in addition to other tools that expect an
> Ethernet link layer. We'd like to support them on top of IPoIB.
See routing. The code is already done.
> I don't see in other alternatives a solution for the problem we're
> trying to solve. If there are changes/suggestions to improve eIPoIB
> netdev driver to avoid "messing with the link layer" and make it
> acceptable, we can discuss and apply them.
Nothing needs to be applied the code is done. Routing from
IPoE to IPoIB works.
There is nothing in what anyone has posted as requirements that needs
work to implement.
I totally fail to see how getting packets of of the VM as ethernet
frames, and then IP layer routing those packets over IP is not an
option. What requirement am I missing.
All VMs should suport that mode of operation, and certainly the kernel
does.
Implementations involving bridges like macvlan and macvtap are
performance optimizations, and the optimizations don't even apply in
areas like 802.11, where only one mac address is supported per adapter.
Bridging can ocassionally also be an administrative simplification as
well, but you should be able to achieve the a similar simplification
with a dhcprelay and proxy arp.
Eric
^ permalink raw reply
* Re: [RFC][PATCH v2] net-tcp: TCP/IP stack bypass for loopback connections
From: David Miller @ 2012-08-07 0:24 UTC (permalink / raw)
To: brutus; +Cc: edumazet, netdev
In-Reply-To: <1344298429-19765-1-git-send-email-brutus@google.com>
From: "Bruce \"Brutus\" Curtis" <brutus@google.com>
Date: Mon, 6 Aug 2012 17:13:49 -0700
> + /*
> + * If friends haven't been made yet, our sk_friend
> + * still == NULL, then update with the ACK's friend
> + * value (the listen()er's sock addr) which is used
> + * as a place holder.
> + */
> + atomic_long_cmpxchg(&sk->sk_friend, 0,
> + (u64)skb->friend);
You probably want plain:
cmpxchg(&sk->sk_friend, NULL, skb->friend);
here.
Rather than using an expression that implies an equivalence between
the types 'long' and 'void *'
^ permalink raw reply
* Re: [PATCH V2 09/12] net/eipoib: Add main driver functionality
From: Ali Ayoub @ 2012-08-07 0:14 UTC (permalink / raw)
To: David Miller
Cc: ebiederm, ogerlitz, roland, netdev, sean.hefty, erezsh, dledford
In-Reply-To: <20120803.163627.1867181085116225405.davem@davemloft.net>
On 8/3/2012 4:36 PM, David Miller wrote:
> From: Ali Ayoub <ali@mellanox.com>
> Date: Fri, 03 Aug 2012 15:39:36 -0700
>
>> Users would like to use sockets API from the VM without re-writing their
>> applications on top of IB verbs, this driver meant to allow such a user
>> to do so.
>
> That's what IPoIB was for, the application writers who don't want to have
> to be knowledgable about IB verbs.
>
> You're messing with the link layer here, and that's what is upsetting me.
>
> It's a complete cop-out to changing the VM tools and emulators properly to
> handle a new link layer.
>
> The applications writers already have a way to use IB whilst using
> something familiar, like IPv4, via IPoIB. You're doing something
> completely different here, and it stinks.
Indeed, IPoIB driver meant to allow IP applications to run over
InfiniBand, but IPoIB cannot serve IPoE traffic.
The goal of eIPoIB driver to show to the user an Ethernet L2 netdev; by
translating IPoE packets to IPoIB. It keeps the same IPoIB wire
protocol, and exposes to the host an ethX interface, all IPoIB packets
are then translated to IPoIB.
Among other things, the main benefit we're targeting is to allow IPoE
traffic within the VM to go through the (Ethernet) vBridge down to the
eIPoIB PIF, and eventually to IPoIB and to the IB network.
In Para virtualized environment, the VM emulator sends/receives packets
with Ethernet header, and the vBridge also performs L2 switching based
on the Ethernet header, in addition to other tools that expect an
Ethernet link layer. We'd like to support them on top of IPoIB.
I see your point to change the the tools and VM emulations to handle
IPoIB link layer, but this involves not only changing many
components/layers such netfront/vbridge/vconfig/etc.. but also -unlike
Ethernet- having IPoIB-aware network device emulation in the VM domain
requires giving access from the VM to the IB Hardware, and this
association will break upon VM migration, as Tsirkin indicated in the
other Email.
Another issue with IPoIB-aware emulator, is that the IPoIB frame doesn't
include the destination link layer per data packet (RFC 4391), therefor
the neighbor address needs to be passed from the VM domain down to the
ipoib-aware vBridge.
I don't see in other alternatives a solution for the problem we're
trying to solve. If there are changes/suggestions to improve eIPoIB
netdev driver to avoid "messing with the link layer" and make it
acceptable, we can discuss and apply them.
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox