Re: [PATCH] TOMOYO: Add garbage collector support. (v2)

Paul E. McKenney
2009-05-27T00:16:32Z

On Mon, May 25, 2009 at 09:41:31AM +0900, Tetsuo Handa wrote:
> ------- Forwarded Message
> From: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
> To: serue@us.ibm.com, jmorris@namei.org
> Cc: haradats@nttdata.co.jp, takedakn@nttdata.co.jp
> Subject: Re: [PATCH] TOMOYO: Add garbage collector support. (v2)
> Date: Sat, 23 May 2009 11:05:24 +0900
>
> Thank you for reviewing.
>
> Serge E. Hallyn wrote:
> > So yes, you might be able to get more review of your patch
> > if you split it up into:
> >
> > 1. move allocations outside of semaphore
> > 2. add proper refcounting
> > 3. get rid of ->is_deleted
>
> I'm ready to post part (1).
>
> security/tomoyo/common.c | 80 ++++++---------------
> security/tomoyo/common.h | 2
> security/tomoyo/domain.c | 97 ++++++++++++-------------
> security/tomoyo/file.c | 133 ++++++++++++++++++-----------------
> security/tomoyo/realpath.c | 169 ++++++++++++++-------------------------------
> security/tomoyo/realpath.h | 7 -
> 6 files changed, 200 insertions(+), 288 deletions(-)
>
> http://svn.sourceforge.jp/cgi-bin/viewcvs.cgi/trunk/2.2.x/tomoyo-lsm/patches/tomoyo-move-sleeping-operations-to-outside-semaphore.patch?view=markup&revision=2579&root=tomoyo
>
> But I think I won't get rid of ->is_deleted. Reasons are shown below.
>
> > However, the way you went about it here is weird too. The big
> > cookie list that pins items, instead of refcounts, is very un-linuxy.
> > Is there a reason why you can't use more of a read-copy-update
> > approach? Keep a refcount on the objects, get rid of ->is_deleted,
> > remove the objects from their list instead of setting is_deleted
> > (so that after one rcu cycle no new readers can come in and increment
> > the refcount), wait an rcu cycle, and then free if refcount is 0?
>
> All items are linked using "struct list_head".
> TOMOYO uses "struct tomoyo_io_buffer" with three "struct list_head" members
> named ->read_var1 / ->read_var2 / ->write_var1 for handling read()/write() via
> securityfs interface. These members act as cookies.
>
> Within a single read() request, it is possible to protect the list by using
> down_read(). But an administrator won't read out all items in a single read()
> request. Therefore, TOMOYO stores the item which is scheduled to be accessed on
> next read() request into ->read_var1 and ->read_var2 .
>
> Similar situation for write() request. An administrator won't write all items
> in a single write() request. Therefore, TOMOYO stores the item which is
> accessed on next write() request into ->write_var1 .
>
> The ->read_var1 / ->read_var2 / ->write_var1 act as cookies.
>
> Yes, I can add a refcounter to all items which is only used for remembering
> whether an item is stored in ->read_var1 / ->read_var2 / ->write_var1 or not.
>
> When the item which ->read_var1 / ->read_var2 / ->write_var1 refer changes,
> we have to decrement the refcount of the object pointed by old ->read_var1 /
> ->read_var2 / ->write_var1 and increment the refcount of the object pointed by
> new ->read_var1 / ->read_var2 / ->write_var1 before releasing the lock.
>
> I pinned the address of "struct list_head" into the cookie list so that I don't
> need to increment/decrement of an item's refcounter while guaranteeing that the
> item pointed by the cookie list shall remain valid after up_read()/up_write().
>
> > where tomoyo_used_by_cookie then walks every cookie, meaning every
> > tomoyo object, seems hugely expensive to me. I know it's only at
> > policy load, but...
> The cookie list approach will save memory compared to the refcounter approach
> because the number of cookies in the cookie list will be smaller than
> the number of items in all lists except the cookie list.
>
> Even if we defer releasing memory of a deleted item, we can't remove an
> item from the list when an administrator deleted the item.
> Removing from the list (i.e. list_del()) will modify ->next and ->prev pointer
> of the item. If the item was scheduled to be accessed on next read() request,
> TOMOYO will crash by dereferencing ->next pointer of the item.

The list_del_rcu() primitive is designed for removing elements from
lists that have concurrent readers, and it therefore avoids changing the
->next pointer. That said, I don't immediately see whether or not there
is some other reason you need to keep it on the list. And do you need
the ->prev pointer to stay valid? If not, you might be able to use it
in place of the ->is_deleted flag.

> Use of RCU does not help here because we need to keep the item valid as long as
> the item is referred by ->read_var1 or ->read_var2 or ->write_var1 .

You would indeed need some way of tracking those references. One
approach is to make the RCU callback check to see if any of them
reference the to-be-deleted object, reposting itself if so. This
approach assumes that such a reference is short-lived, of course.

If the ->read_var1 and other references are long-lived, could you
post an RCU callback when the last such reference was removed?

> The ->is_deleted flag is needed for skipping an item in read() request
> because TOMOYO can't modify ->next and ->prev pointer of an item when that item
> is scheduled to be accessed on next read() request.
>
> My opinion is that the refcounter approach might replace the cookie list
> approach, but the refcounter approach can't get rid of ->is_deleted flag.

Some RCU algorithms do use something similar to the ->is_deleted flag.

Thanx, Paul

> > > (2) Should TOMOYO have GC support?
> >
> > Well if your only audience is meant to be tiny embedded systems which
> > will never update policy, then heck maybe not. But it certainly is
> > weird not to.
>
> The non-LSM version of TOMOYO is "GC support free" but saves a lot of memory
> by using "singly linked list", "read lock free", "refcounter free" approach.
>
> Maybe we should add a refcounter to all items and avoid the cookie list.
> In that case, we can allow users to determine via the kernel config whether
> TOMOYO supports GC or not. If GC support is not chosen via the kernel config,
> TOMOYO can save memory by using "singly linked list", "read lock free",
> "refcounter free" approach.
>
> ------- End of Forwarded Message
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/