replace slightly obscure while loops with for_each_zone and
for_each_pgdat macros, this version has the added optimisation
of skipping empty zones (thanks to William Lee Irwin)
--
Hi Linus, [retransmit #1]
this patch cleans up the VM a little bit and has a microoptimisation
to skip zones of size zero. You can apply this mail or pull the
changes from:
bk://linuxvm.bkbits.net/linux-2.5-for-linus/
please apply,
thanks,
Rik
# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher.
# This patch includes the following deltas:
# ChangeSet 1.456 -> 1.457
# include/linux/mmzone.h 1.8 -> 1.9
# mm/page_alloc.c 1.44 -> 1.45
# mm/vmscan.c 1.59 -> 1.60
# mm/bootmem.c 1.8 -> 1.9
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 02/04/11 [email protected] 1.457
# replace slightly obscure while loops with for_each_zone and
# for_each_pgdat macros, this version has the added optimisation
# of skipping empty zones (thanks to William Lee Irwin)
# --------------------------------------------
#
diff -Nru a/include/linux/mmzone.h b/include/linux/mmzone.h
--- a/include/linux/mmzone.h Thu Apr 11 21:23:50 2002
+++ b/include/linux/mmzone.h Thu Apr 11 21:23:50 2002
@@ -157,6 +157,62 @@
extern pg_data_t contig_page_data;
+/**
+ * for_each_pgdat - helper macro to iterate over all nodes
+ * @pgdat - pg_data_t * variable
+ *
+ * Meant to help with common loops of the form
+ * pgdat = pgdat_list;
+ * while(pgdat) {
+ * ...
+ * pgdat = pgdat->node_next;
+ * }
+ */
+#define for_each_pgdat(pgdat) \
+ for (pgdat = pgdat_list; pgdat; pgdat = pgdat->node_next)
+
+/*
+ * next_zone - helper magic for for_each_zone()
+ * Thanks to William Lee Irwin III for this piece of ingenuity.
+ */
+static inline zone_t *next_zone(zone_t *zone)
+{
+ pg_data_t *pgdat = zone->zone_pgdat;
+
+ do {
+ if (zone - pgdat->node_zones < MAX_NR_ZONES - 1)
+ zone++;
+
+ else if (pgdat->node_next) {
+ pgdat = pgdat->node_next;
+ zone = pgdat->node_zones;
+ } else
+ zone = NULL;
+ /* Skip zones of size 0 ... */
+ } while (zone && !zone->size);
+
+ return zone;
+}
+
+/**
+ * for_each_zone - helper macro to iterate over all memory zones
+ * @zone - zone_t * variable
+ *
+ * The user only needs to declare the zone variable, for_each_zone
+ * fills it in. This basically means for_each_zone() is an
+ * easier to read version of this piece of code:
+ *
+ * for(pgdat = pgdat_list; pgdat; pgdat = pgdat->node_next)
+ * for(i = 0; i < MAX_NR_ZONES; ++i) {
+ * zone_t * z = pgdat->node_zones + i;
+ * ...
+ * }
+ * }
+ */
+#define for_each_zone(zone) \
+ for(zone = pgdat_list->node_zones; zone; zone = next_zone(zone))
+
+
#ifndef CONFIG_DISCONTIGMEM
#define NODE_DATA(nid) (&contig_page_data)
diff -Nru a/mm/bootmem.c b/mm/bootmem.c
--- a/mm/bootmem.c Thu Apr 11 21:23:50 2002
+++ b/mm/bootmem.c Thu Apr 11 21:23:50 2002
@@ -338,12 +338,11 @@
pg_data_t *pgdat = pgdat_list;
void *ptr;
- while (pgdat) {
+ for_each_pgdat(pgdat)
if ((ptr = __alloc_bootmem_core(pgdat->bdata, size,
align, goal)))
return(ptr);
- pgdat = pgdat->node_next;
- }
+
/*
* Whoops, we cannot satisfy the allocation request.
*/
diff -Nru a/mm/page_alloc.c b/mm/page_alloc.c
--- a/mm/page_alloc.c Thu Apr 11 21:23:50 2002
+++ b/mm/page_alloc.c Thu Apr 11 21:23:50 2002
@@ -482,14 +482,10 @@
{
unsigned int sum;
zone_t *zone;
- pg_data_t *pgdat = pgdat_list;
sum = 0;
- while (pgdat) {
- for (zone = pgdat->node_zones; zone < pgdat->node_zones + MAX_NR_ZONES; zone++)
+ for_each_zone(zone)
sum += zone->free_pages;
- pgdat = pgdat->node_next;
- }
return sum;
}
@@ -501,7 +497,7 @@
pg_data_t *pgdat = pgdat_list;
unsigned int sum = 0;
- do {
+ for_each_pgdat(pgdat) {
zonelist_t *zonelist = pgdat->node_zonelists + (GFP_USER & GFP_ZONEMASK);
zone_t **zonep = zonelist->zones;
zone_t *zone;
@@ -512,9 +508,7 @@
if (size > high)
sum += size - high;
}
-
- pgdat = pgdat->node_next;
- } while (pgdat);
+ }
return sum;
}
@@ -522,13 +516,12 @@
#if CONFIG_HIGHMEM
unsigned int nr_free_highpages (void)
{
- pg_data_t *pgdat = pgdat_list;
+ pg_data_t *pgdat;
unsigned int pages = 0;
- while (pgdat) {
+ for_each_pgdat(pgdat)
pages += pgdat->node_zones[ZONE_HIGHMEM].free_pages;
- pgdat = pgdat->node_next;
- }
+
return pages;
}
#endif
diff -Nru a/mm/vmscan.c b/mm/vmscan.c
--- a/mm/vmscan.c Thu Apr 11 21:23:50 2002
+++ b/mm/vmscan.c Thu Apr 11 21:23:50 2002
@@ -655,10 +655,8 @@
do {
need_more_balance = 0;
- pgdat = pgdat_list;
- do
+ for_each_pgdat(pgdat)
need_more_balance |= kswapd_balance_pgdat(pgdat);
- while ((pgdat = pgdat->node_next));
} while (need_more_balance);
}
@@ -681,12 +679,11 @@
{
pg_data_t * pgdat;
- pgdat = pgdat_list;
- do {
+ for_each_pgdat(pgdat) {
if (kswapd_can_sleep_pgdat(pgdat))
continue;
return 0;
- } while ((pgdat = pgdat->node_next));
+ }
return 1;
}
On Mon, 15 Apr 2002, Rik van Riel wrote:
> replace slightly obscure while loops with for_each_zone and
> for_each_pgdat macros, this version has the added optimisation
> of skipping empty zones (thanks to William Lee Irwin)
I'd suggest against making this kind of complicated inlien functions, and
I also don't see why the for_each_zone() isn't a simpler doubly nested
for-loop instead of being forced into a less obvious iterative loop?
In short, this looks syntactically simple, but the syntactic simplicity
comes at the expense of a unnecessarily complex implementation.
Linus
On Mon, 15 Apr 2002, Linus Torvalds wrote:
> On Mon, 15 Apr 2002, Rik van Riel wrote:
> > replace slightly obscure while loops with for_each_zone and
> > for_each_pgdat macros, this version has the added optimisation
> > of skipping empty zones (thanks to William Lee Irwin)
>
> I'd suggest against making this kind of complicated inlien functions, and
> I also don't see why the for_each_zone() isn't a simpler doubly nested
> for-loop instead of being forced into a less obvious iterative loop?
Because code that doesn't care about pgdats shouldn't have to
learn about them, IMHO. I used to have the doubly nested for
loop in -rmap, but William Irwin came up with a way to make
it a singly nested loop for code that only cares about zones.
> In short, this looks syntactically simple, but the syntactic simplicity
> comes at the expense of a unnecessarily complex implementation.
Since it was mostly done to clean up code I guess it makes
sense to simplify the thing a bit, if possible.
However, I really don't like the fact of teaching now-simple
VM code about pgdats again ;)
regards,
Rik
--
http://www.linuxsymposium.org/2002/
"You're one of those condescending OLS attendants"
"Here's a nickle kid. Go buy yourself a real t-shirt"
http://www.surriel.com/ http://distro.conectiva.com/
On Mon, 15 Apr 2002, Rik van Riel wrote:
>
> However, I really don't like the fact of teaching now-simple
> VM code about pgdats again ;)
Well, you don't actually have to teach it about pgdats, but try out how
much simpler the actual implementation is if you were to just add a
"endzone" macro, allowing the macros to do nesting.
Once you do that, you can basically expand the thing any which way,
something like
#define for_each_zone(zone) \
do { pg_data_t * __pgdat; \
for (__pgdat = pgdat_list; __pgdat; __pgdat = __pgdat->next) { \
int __i; \
for (i = 0; i < MAX_ZONES; i++) { \
zone = pgdat->node_zones; \
if (!zone->size) \
break; \
do { \
#define end_zone \
while (0); \
} \
} \
} while (0)
Which requires the user to use something like
for_each_zone(zone) {
...
} end_zone;
but doesn't need changing the double loop into a artificial single loop.
Linus
On Mon, 15 Apr 2002, Linus Torvalds wrote:
>
> Which requires the user to use something like
>
> for_each_zone(zone) {
> ...
> } end_zone;
Side note: I should probably have made this the standard notation for the
"for_each_xxx ()" macros, because having an "end_xxx" macro means that you
can start using things like "do { ... } while (x)" loops for the control
flow, which is often easier for the compiler to optimize (ie if the first
element is always valid, and you don't need a condition going in, which is
often true).
It does, of course, end up polluting the name-space a bit more.
Linus
On Mon, Apr 15, 2002 at 02:08:54PM -0700, Linus Torvalds wrote:
> Which requires the user to use something like
>
> for_each_zone(zone) {
> ...
> } end_zone;
>
> but doesn't need changing the double loop into a artificial single loop.
Bah, wli's version is so much nicer to use - in my eyes that justifies
the additional complexity in the macro.
> Because code that doesn't care about pgdats shouldn't have to
> learn about them, IMHO. I used to have the doubly nested for
> loop in -rmap, but William Irwin came up with a way to make
> it a singly nested loop for code that only cares about zones.
Can't you just have the simple single and double loops in mmzone.h,
seperated by a #ifdef CONFIG_DISCONTIGMEM?
I like the general abstraction idea of where you're going though.
Is there a for_each_node already? Can't see one:
#define for_each_node(nid) \
for (nid = 0; nid < numnodes; nid++)
would allow us to change the assumption that nodes are numbered
contiguously, starting from 0, more easily later on ... ?
M.
On Mon, 15 Apr 2002, Linus Torvalds wrote:
> Which requires the user to use something like
>
> for_each_zone(zone) {
> ...
> } end_zone;
You just pinpointed the reason we didn't do what you wrote down ;)
We can change the code to your liking, though.
Rik
--
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/ http://distro.conectiva.com/
On Mon, 15 Apr 2002, Linus Torvalds wrote:
>> Which requires the user to use something like
>>
>> for_each_zone(zone) {
>> ...
>> } end_zone;
Ow... this is exactly what I was trying to avoid.
On Mon, Apr 15, 2002 at 02:17:22PM -0700, Linus Torvalds wrote:
> Side note: I should probably have made this the standard notation for the
> "for_each_xxx ()" macros, because having an "end_xxx" macro means that you
> can start using things like "do { ... } while (x)" loops for the control
> flow, which is often easier for the compiler to optimize (ie if the first
> element is always valid, and you don't need a condition going in, which is
> often true).
> It does, of course, end up polluting the name-space a bit more.
> Linus
This is typically either the outer loop or used in things that just aren't
time critical (at least not in comparison to deeper loop nesting levels).
This isn't my magnum opus by a longshot (or at least I hope it isn't) so
I won't scream too loud, but I think it's pretty much done right as is.
Cheers,
Bill
On Mon, Apr 15, 2002 at 04:20:58PM -0700, William Lee Irwin III wrote:
> I won't scream too loud, but I think it's pretty much done right as is.
Regardless if that's the cleaner implementation or not, I don't see much
the point of merging those cleanups in 2.4 right now: it won't make any
functional difference to users and it's only a self contained code
cleanup, while other patches that make a runtime difference aren't
merged yet.
Andrea
On Tue, Apr 16, 2002 at 02:44:58AM +0200, Andrea Arcangeli wrote:
> On Mon, Apr 15, 2002 at 04:20:58PM -0700, William Lee Irwin III wrote:
> > I won't scream too loud, but I think it's pretty much done right as is.
>
> Regardless if that's the cleaner implementation or not, I don't see much
> the point of merging those cleanups in 2.4 right now: it won't make any
> functional difference to users and it's only a self contained code
> cleanup, while other patches that make a runtime difference aren't
> merged yet.
>
One set (1 of 3) of you vm patches have already gone into 2.4.19-pre and
IMHO, each set should go into a major release seperately (2.4.19/20/21).
There are so many more people who use the released versions than the -pre
versions of the kernel.
No matter how much someone can go through their own code and say "it's
ready" there's always a good chance there is some bug that will trigger
under testing. Also, Andrew found a problem with your locking changes when
he split up your patch, and at the time you were saying it is ready and
there were no bug reports against in...
Now I doubt that there is anything to worry about, we are talking about a
stable kernel series here.
Does this patch conflict in any way with your vm patches? If not they
should be able to co-exist.
On Tue, Apr 16, 2002 at 02:44:58AM +0200, Andrea Arcangeli wrote:
> On Mon, Apr 15, 2002 at 04:20:58PM -0700, William Lee Irwin III wrote:
> > I won't scream too loud, but I think it's pretty much done right as is.
>
> Regardless if that's the cleaner implementation or not, I don't see much
> the point of merging those cleanups in 2.4 right now: it won't make any
> functional difference to users and it's only a self contained code
> cleanup, while other patches that make a runtime difference aren't
> merged yet.
Sorry to say it, but if you want patches to be merged, why
don't you submit them ?
regards,
Rik
--
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/ http://distro.conectiva.com/
On Tue, 16 Apr 2002, Andrea Arcangeli wrote:
> On Mon, Apr 15, 2002 at 04:20:58PM -0700, William Lee Irwin III wrote:
> > I won't scream too loud, but I think it's pretty much done right as is.
>
> Regardless if that's the cleaner implementation or not, I don't see
> much the point of merging those cleanups in 2.4 right now: it won't
> make any functional difference to users and it's only a self contained
> code cleanup,
Thats exactly why they can be merged easily: They are self contained code
cleanups, as you said.
> while other patches that make a runtime difference aren't merged yet.
They aren't merged yet because they are intrusive and, in your case (-aa
VM patches), they are not obviously correct and are hard to understand.
We're making progress, though. The writeout scheduling changes (which were
easy for me to understand) have been merged already.
On Tue, Apr 16, 2002 at 01:27:26AM -0300, Rik van Riel wrote:
> On Tue, Apr 16, 2002 at 02:44:58AM +0200, Andrea Arcangeli wrote:
> > On Mon, Apr 15, 2002 at 04:20:58PM -0700, William Lee Irwin III wrote:
> > > I won't scream too loud, but I think it's pretty much done right as is.
> >
> > Regardless if that's the cleaner implementation or not, I don't see much
> > the point of merging those cleanups in 2.4 right now: it won't make any
> > functional difference to users and it's only a self contained code
> > cleanup, while other patches that make a runtime difference aren't
> > merged yet.
>
> Sorry to say it, but if you want patches to be merged, why
> don't you submit them ?
I submitted these in a past email:
ftp://ftp.us.kernel.org/pub/linux/kernel/people/andrea/patches/v2.4/2.4.19pre5/vm-33/aa-*
Andrea
On Mon, Apr 15, 2002 at 06:30:16PM -0700, Mike Fedyk wrote:
> under testing. Also, Andrew found a problem with your locking changes when
> he split up your patch, and at the time you were saying it is ready and
> there were no bug reports against in...
btw, it was a problem only for ext3.
> Does this patch conflict in any way with your vm patches? If not they
> should be able to co-exist.
it will generate rejects, but that's not the problem. My point is that
your same argument about merging in later kernels, stable kernel tree,
could be applied to patches that makes no difference to users too.
Andrea
On Mon, 15 Apr 2002, Mike Fedyk wrote:
> No matter how much someone can go through their own code and say "it's
> ready" there's always a good chance there is some bug that will trigger
> under testing. Also, Andrew found a problem with your locking changes when
> he split up your patch, and at the time you were saying it is ready and
> there were no bug reports against in...
If you are going to reject code from people who send in code which turns
out to have bugs you are going to have a VERY small set of submitters.
It's good to have someone else read the code, for breakup or whatever, but
to avoid cleanup in a stable kernel seems long term the wrong direction.
--
bill davidsen <[email protected]>
CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.
On Mon, 15 Apr 2002, Linus Torvalds wrote:
> On Mon, 15 Apr 2002, Linus Torvalds wrote:
> >
> > Which requires the user to use something like
> >
> > for_each_zone(zone) {
> > ...
> > } end_zone;
>
> Side note: I should probably have made this the standard notation for the
> "for_each_xxx ()" macros, because having an "end_xxx" macro means that you
> can start using things like "do { ... } while (x)" loops for the control
> flow, which is often easier for the compiler to optimize (ie if the first
> element is always valid, and you don't need a condition going in, which is
> often true).
>
> It does, of course, end up polluting the name-space a bit more.
Ugh. If we're going to use such ugly things, it would be nice if they were
do_zone/while_zone instead of being suggestive of a for loop.
--
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."
On Tue, 16 Apr 2002, Oliver Xymoron wrote:
> On Mon, 15 Apr 2002, Linus Torvalds wrote:
> > On Mon, 15 Apr 2002, Linus Torvalds wrote:
> > >
> > > Which requires the user to use something like
> > >
> > > for_each_zone(zone) {
> > > ...
> > > } end_zone;
> Ugh. If we're going to use such ugly things, it would be nice if they were
> do_zone/while_zone instead of being suggestive of a for loop.
Ummm, it _is_ a for loop.
Rik
--
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/ http://distro.conectiva.com/
On Tue, 16 Apr 2002, Rik van Riel wrote:
> On Tue, 16 Apr 2002, Oliver Xymoron wrote:
> > On Mon, 15 Apr 2002, Linus Torvalds wrote:
> > > On Mon, 15 Apr 2002, Linus Torvalds wrote:
> > > >
> > > > Which requires the user to use something like
> > > >
> > > > for_each_zone(zone) {
> > > > ...
> > > > } end_zone;
>
> > Ugh. If we're going to use such ugly things, it would be nice if they were
> > do_zone/while_zone instead of being suggestive of a for loop.
>
> Ummm, it _is_ a for loop.
Conceptually, sure, but the underlying macros Linus suggested made it
do/while. As the do/while form is the only control structure in C where we
have something that looks like an expression after a block, naming it for_
seems terribly incongruous. Naming it do_/while_ would make it slightly
less ugly, at least to my eyes, and serve to remind that both parts are
essential.
--
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."
On 2002.04.16 Rik van Riel wrote:
>On Tue, 16 Apr 2002, Oliver Xymoron wrote:
>> On Mon, 15 Apr 2002, Linus Torvalds wrote:
>> > On Mon, 15 Apr 2002, Linus Torvalds wrote:
>> > >
>> > > Which requires the user to use something like
>> > >
>> > > for_each_zone(zone) {
>> > > ...
>> > > } end_zone;
>
>> Ugh. If we're going to use such ugly things, it would be nice if they were
>> do_zone/while_zone instead of being suggestive of a for loop.
>
>Ummm, it _is_ a for loop.
>
Perhaps a silly change like
for_all_zone -> forall_zone
for_all_page -> forall_page
changes the point of view of some people. Some languages implement a 'forall'
iteration. And looks better...
--
J.A. Magallon # Let the source be with you...
mailto:[email protected]
Mandrake Linux release 8.3 (Cooker) for i586
Linux werewolf 2.4.19-pre6-jam2 #2 SMP Tue Apr 16 00:29:36 CEST 2002 i686
On Tue, Apr 16, 2002 at 03:44:18PM +0200, Andrea Arcangeli wrote:
> On Mon, Apr 15, 2002 at 06:30:16PM -0700, Mike Fedyk wrote:
> > under testing. Also, Andrew found a problem with your locking changes when
> > he split up your patch, and at the time you were saying it is ready and
> > there were no bug reports against in...
>
> btw, it was a problem only for ext3.
>
Right, I forgot to mention that.
> > Does this patch conflict in any way with your vm patches? If not they
> > should be able to co-exist.
>
> it will generate rejects, but that's not the problem. My point is that
> your same argument about merging in later kernels, stable kernel tree,
> could be applied to patches that makes no difference to users too.
>
True. Has Rik's cleanup already been merged into 2.5?
> Andrea
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
>
On Tue, Apr 16, 2002 at 10:00:36AM -0400, Bill Davidsen wrote:
> On Mon, 15 Apr 2002, Mike Fedyk wrote:
>
> > No matter how much someone can go through their own code and say "it's
> > ready" there's always a good chance there is some bug that will trigger
> > under testing. Also, Andrew found a problem with your locking changes when
> > he split up your patch, and at the time you were saying it is ready and
> > there were no bug reports against in...
>
> If you are going to reject code from people who send in code which turns
> out to have bugs you are going to have a VERY small set of submitters.
No that's not what I was saying.
> It's good to have someone else read the code, for breakup or whatever, but
> to avoid cleanup in a stable kernel seems long term the wrong direction.
>
Exactly. I'm just saying that you will get more eyes on the code and less
possible detrimental impact (if any, which I doubt) if the patches don't all
go into one set of -pre patches but spread out over a few releases
(2.4.19,20 and possibly 21). The -pre kernels get testing, but not nearly
as much as the releases do. Test the -pre and -rc kernels as much as
possible, but also know that something might be flushed out by some people
that only use the released kernels (non -pre or -rc).
Mike