Messages in this thread | | | Date | Tue, 26 May 2009 17:16:13 -0700 | From | "Paul E. McKenney" <> | Subject | Re: [PATCH] TOMOYO: Add garbage collector support. (v2) |
| |
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/
| |