Hello, Boaz.
On Thu, Nov 20, 2014 at 02:36:53PM +0200, Boaz Harrosh wrote:
> Actually with my proposed change to "the code you submitted here"
> there are *less* unnecessary allocations. In both our imp we have a
> waste when element already exist in the tree, and your imp already
> waists an allocation in every pset_preload()
>
> And again you are talking about a future undefined "what if", let
> us look at the very sound imp you proposed here with rbtree and
> do the best we can with that one.
Preloading is an established pattern and a pretty effective one at
that. It allows its users to not worry about carrying the state
explicitly while allowing the preloaded allocation to be cached across
multiple insertions.
Whether ptrset needs it or not is debatable. If it didn't need to be
shared between block and chardevs, I prolly would have just open coded
it with linked list. But being a generic library feature which isn't
too different from other memory allocating indexing data structures, I
think it'd be better to follow the established pattern rather than
creating another one-off behavior. If we demote this to something
which is shared only between block and char devs, we can go simpler
and less versatile. Where should it go tho?
> Again Theoretical. With your current code the only failing I see
> from add() is allocation, so with my imp it will never fail. One
> thing good with embedded list_heads is the void returning add.
> And so with my proposition: void returning add.
Sure, if you look at just these two instances. We can just require
preloading and drop @gfp from the insertion function too. -EEXIST can
be avoided too, so let's drop the return value entirely.
Again, the problem is that it's implemented as a generic lib feature,
so it needs to consider how different use cases can be served and we
have an established pattern which proved to be effective over time for
these types of data structures and that's the pattern being followed
here.
> When some new imp will be needed we can cross the bridge then.
>
> For now you have convinced me that an rbtree is good, and I want to
> solve the preemption-disable, none interrupt ugliness, per-cpu vars,
> as well as the double alloc in the normal lots-of-free-memory case.
It's a reserve which is kept around, one per CPU at most, which also
allows us to avoid spurious frees on insertion attempts which don't
consume the reserve. If your point is that we don't need ptrset as a
generic lib thing, this can definitely be simpler but otherwise I'm
not sure what you're arguing. We have an established pattern to make
prealloactions easier for generic lib functions. Why wouldn't we use
that and make things simpler for its users?
> > so
> > overall it seems better to defer the allocation error to the actual
> > insertion point.
>
> That one I did not understand.
So, w/o preloading, you would do,
error = insert();
if (error)
handle error;
W/ preloading, one way to do it is,
if (preload())
handle -ENOMEM;
lock;
error = insert();
if (error)
handle error which can't be -ENOMEM;
unlock;
preload_end();
Another way is
preload(); // can't fail
lock;
error = insert();
if (error)
handle error;'
unlock;
preload_end();
Both ways have pros and cons. The latter seems to lead to simpler
code in general. Not always, but the overall.
> > It also makes conceptual sense. The preloading
> > simply upgrades the allocation mask the insertion operation uses.
>
> How is "upgrades", better then "always have the best mask"
Hah? What are you talking about? So,
preload(GFP_KERNEL);
lock;
insert(GFP_NOWAIT);
unlock;
preload_end();
can be considered as insert() allocating memory using GFP_KERNEL.
That's what preallocation does. My point was that deferring
allocation error to insert() time allows considering the above code
like the following.
lock;
insert(GFP_KERNEL);
unlock;
And that's why the pattern usually leads to simpler code - it doesn't
create a new failure point.
Thanks.
--
tejun
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
