Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
James Morris wrote:
> > > It seems that standard kernel list API does not have singly-linked list
> > > manipulation.
> > > I'm considering the following list manipulation API.
>
> I'm pretty sure that the singly linked list idea has been rejected a few
> times. Just use the existing API.
>
OK. I posted new one that uses existing API at
http://lkml.org/lkml/2007/10/11/140 .
By the way, what do you think of new primitives shown below?
I'd like to use list_for_each_cookie() and list_add_tail_mb() if acceptable.
- Start of code -
/** Existing API **/
#include
#include
static inline void mb(void) {;}
static inline void prefetch(void *p) {;}
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ const typeof( ((type *)0)->member )
*__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );})
#define list_entry(ptr, type, member) container_of(ptr, type, member)
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { , }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
/** Proposed API **/
/**
* list_for_each_cookie - iterate over a list with cookie.
* @pos:the list_head to use as a loop cursor.
* @cookie: the list_head to use as a cookie.
* @head: the head for your list.
*
* Same with list_for_each except that this primitive uses cookie
* so that we can continue iteration.
*/
#define list_for_each_cookie(pos, cookie, head) \
for ((cookie) || ((cookie) = (head)), pos = (cookie)->next; \
prefetch(pos->next), pos != (head) || ((cookie) = NULL); \
(cookie) = pos, pos = pos->next)
/**
* list_add_tail_mb - add a new entry with memory barrier.
* @new: new entry to be added.
* @head: list head to add it before.
*
* Same with list_add_tail_rcu() except that this primitive uses mb()
* so that we can traverse forwards using list_for_each() and
* list_for_each_cookie().
*/
static inline void list_add_tail_mb(struct list_head *new,
struct list_head *head)
{
struct list_head *prev = head->prev;
struct list_head *next = head;
new->next = next;
new->prev = prev;
mb();
next->prev = new;
prev->next = new;
}
/** Usage example **/
struct something {
struct list_head list;
int v;
};
static LIST_HEAD(something_list);
int main(int argc, char *argv[]) {
struct something *ptr;
struct list_head *pos;
struct list_head *cookie = NULL;
int i;
for (i = 0; i < 10; i++) {
printf("add %d\n", i);
ptr = malloc(sizeof(*ptr));
ptr->v = 10 + i;
list_add_tail_mb(&(ptr->list), _list);
}
printf("dump\n");
i = 0;
do {
list_for_each_cookie(pos, cookie, _list) {
ptr = list_entry(pos, struct something, list);
if (++i % 4 == 0) { /* Interrupt such as buffer-full. */
printf("break\n");
break;
}
printf("%d\n", ptr->v);
}
} while (cookie);
return 0;
}
- End of code -
Regards.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
Peter Zijlstra wrote:
> > append_function() {
> >
> > down(semaphore_for_write_protect);
> > ...
> > ptr = head;
> > while (ptr->next) ptr = ptr->next;
> > ptr->next = new_entry;
> > ...
> > up(semaphore_for_write_protect);
> >
> > }
>
> If at all possible, use struct mutex.
Fixed in the fourth submission ( http://lkml.org/lkml/2007/10/11/140 ).
Thank you.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
Peter Zijlstra wrote:
append_function() {
down(semaphore_for_write_protect);
...
ptr = head;
while (ptr-next) ptr = ptr-next;
ptr-next = new_entry;
...
up(semaphore_for_write_protect);
}
If at all possible, use struct mutex.
Fixed in the fourth submission ( http://lkml.org/lkml/2007/10/11/140 ).
Thank you.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
James Morris wrote:
It seems that standard kernel list API does not have singly-linked list
manipulation.
I'm considering the following list manipulation API.
I'm pretty sure that the singly linked list idea has been rejected a few
times. Just use the existing API.
OK. I posted new one that uses existing API at
http://lkml.org/lkml/2007/10/11/140 .
By the way, what do you think of new primitives shown below?
I'd like to use list_for_each_cookie() and list_add_tail_mb() if acceptable.
- Start of code -
/** Existing API **/
#include stdio.h
#include stdlib.h
static inline void mb(void) {;}
static inline void prefetch(void *p) {;}
#define offsetof(TYPE, MEMBER) ((size_t) ((TYPE *)0)-MEMBER)
#define container_of(ptr, type, member) ({ const typeof( ((type *)0)-member )
*__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );})
#define list_entry(ptr, type, member) container_of(ptr, type, member)
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { name, name }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
/** Proposed API **/
/**
* list_for_each_cookie - iterate over a list with cookie.
* @pos:the struct list_head to use as a loop cursor.
* @cookie: the struct list_head to use as a cookie.
* @head: the head for your list.
*
* Same with list_for_each except that this primitive uses cookie
* so that we can continue iteration.
*/
#define list_for_each_cookie(pos, cookie, head) \
for ((cookie) || ((cookie) = (head)), pos = (cookie)-next; \
prefetch(pos-next), pos != (head) || ((cookie) = NULL); \
(cookie) = pos, pos = pos-next)
/**
* list_add_tail_mb - add a new entry with memory barrier.
* @new: new entry to be added.
* @head: list head to add it before.
*
* Same with list_add_tail_rcu() except that this primitive uses mb()
* so that we can traverse forwards using list_for_each() and
* list_for_each_cookie().
*/
static inline void list_add_tail_mb(struct list_head *new,
struct list_head *head)
{
struct list_head *prev = head-prev;
struct list_head *next = head;
new-next = next;
new-prev = prev;
mb();
next-prev = new;
prev-next = new;
}
/** Usage example **/
struct something {
struct list_head list;
int v;
};
static LIST_HEAD(something_list);
int main(int argc, char *argv[]) {
struct something *ptr;
struct list_head *pos;
struct list_head *cookie = NULL;
int i;
for (i = 0; i 10; i++) {
printf(add %d\n, i);
ptr = malloc(sizeof(*ptr));
ptr-v = 10 + i;
list_add_tail_mb((ptr-list), something_list);
}
printf(dump\n);
i = 0;
do {
list_for_each_cookie(pos, cookie, something_list) {
ptr = list_entry(pos, struct something, list);
if (++i % 4 == 0) { /* Interrupt such as buffer-full. */
printf(break\n);
break;
}
printf(%d\n, ptr-v);
}
} while (cookie);
return 0;
}
- End of code -
Regards.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
About use of singly-linked list: What my SLL (singly-linked list) holds is bit different from other lists. Almost all lists hold list of elements (e.g. buffer) that are used *temporarily*. Thus, adding to the list and removing from the list are essential. My SLL holds ACL (access control list) entries that are used *permanently* (i.e. throughout the kernel's lifetime). These ACL entries are policy used for MAC (mandatory access control). You don't change MAC's policy without clear reason, do you? Therefore, ACL entries of MAC's policy seldom need to be removed. So I wonder "Remodeling the mechanism of holding ACL entries to support removal of individual entry worth the cost of reference-counter manipulation and the risk of dead-pointers?" Your next question would be "Why are you using SLL for holding elements that are used *permanently*?" "Why not allocate a large memory block and hold all elements in that block?" Yes, you are right. But I can't do so. The reason is explained in "policy file handling" at http://lkml.org/lkml/2007/10/2/56 . About use of list that can't remove elements: I think that many of you are misunderstanding about "When entries are automatically appended to a list". If you run the system in "learning mode" *forever*, it will consume all memory; so DoS attacks are possible. But please be aware that entries are automatically appended only while you are running the system in "learning mode". Also, there is a safeguard mechanism that controls upper limit. These lists consume less than some hundreds KB for embedded systems and/or targeted protection of PC systems, less than 1 MB for complete protection of PC systems. You can see how much memory is used for holding ACL entries via /sys/kernel/security/tomoyo/meminfo interface and you will find that these lists won't consume all memory in your system. When you are running the system in "enforcing mode", no entries are appended automatically; so DoS attacks are impossible. - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
About use of singly-linked list: What my SLL (singly-linked list) holds is bit different from other lists. Almost all lists hold list of elements (e.g. buffer) that are used *temporarily*. Thus, adding to the list and removing from the list are essential. My SLL holds ACL (access control list) entries that are used *permanently* (i.e. throughout the kernel's lifetime). These ACL entries are policy used for MAC (mandatory access control). You don't change MAC's policy without clear reason, do you? Therefore, ACL entries of MAC's policy seldom need to be removed. So I wonder Remodeling the mechanism of holding ACL entries to support removal of individual entry worth the cost of reference-counter manipulation and the risk of dead-pointers? Your next question would be Why are you using SLL for holding elements that are used *permanently*? Why not allocate a large memory block and hold all elements in that block? Yes, you are right. But I can't do so. The reason is explained in policy file handling at http://lkml.org/lkml/2007/10/2/56 . About use of list that can't remove elements: I think that many of you are misunderstanding about When entries are automatically appended to a list. If you run the system in learning mode *forever*, it will consume all memory; so DoS attacks are possible. But please be aware that entries are automatically appended only while you are running the system in learning mode. Also, there is a safeguard mechanism that controls upper limit. These lists consume less than some hundreds KB for embedded systems and/or targeted protection of PC systems, less than 1 MB for complete protection of PC systems. You can see how much memory is used for holding ACL entries via /sys/kernel/security/tomoyo/meminfo interface and you will find that these lists won't consume all memory in your system. When you are running the system in enforcing mode, no entries are appended automatically; so DoS attacks are impossible. - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello. YOSHIFUJI Hideaki wrote: > It is not a good practice. Please free such objects. > BTW, how many objects do you have in the list? It varies from 0 to some thousands, depending on the policy supplied by the administrator and/or the policy appended by "learning mode". Peter Zijlstra wrote: > sounds like a might fine memory leak / dos attack. TOMOYO Linux keeps the policy in CD-R's manner. Thus, once an entry is written, it's pointer is valid forever. TOMOYO Linux's simplicity (singly-linked list with no read_lock) comes from this "keep the policy in CD-R's manner". Yes, it is a kind of memory leak, but is controllable. The kernel no longer requires memory after entering into "enforcing mode". So, attackers can't do DoS attack after entering into "enforcing mode". Regards. - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 2007-10-03 at 23:19 +0900, Tetsuo Handa wrote:
> Hello.
>
> Thank you for pointing out.
>
> Peter Zijlstra wrote:
> > > Currently, TOMOYO Linux avoids read_lock, on the assumption that
> > > (1) First, ptr->next is initialized with NULL.
> > > (2) Later, ptr->next is assigned non-NULL address.
> > > (3) Assigning to ptr->next is done atomically.
> > (4) wmb after asigning ptr->next
> > (5) rmb before reading ptr->next
> Excuse me, but I didn't understand why (4) and (5) are needed.
>
> append_function() {
>
> down(semaphore_for_write_protect);
> ...
> ptr = head;
> while (ptr->next) ptr = ptr->next;
> ptr->next = new_entry;
> ...
> up(semaphore_for_write_protect);
>
> }
It seems to me that this function alone is a reason to argue against
using a singly linked list. I know your patch doesn't actually contain
this as a function but it does use the same logic to append to your
lists. Does the overhead of the second pointer that the regular list
head uses outweigh the O(1) insertion and deletion it provides
(especially in your case)? I know domain transitions are rare but why
use something with O(N) insertion? This could be one reason why there
isn't an slist already in list.h
Dave Quigley
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 3 Oct 2007, YOSHIFUJI Hideaki / µÈÆ£±ÑÌÀ wrote: > In article <[EMAIL PROTECTED]> (at Wed, 3 Oct 2007 23:26:57 +0900), Tetsuo > Handa <[EMAIL PROTECTED]> says: > > > Peter Zijlstra wrote: > > > Also, how do you avoid referencing dead data with your sll? I haven't > > > actually looked at your patches, but the simple scheme you outlined > > > didn't handle the iteration + concurrent removal scenario: > > Regarding my singly-linked list, no entries are removed from the list. It's > > append only (like CD-R media). > > I set is_deleted flag of a entry instead of removing the entry from the > > list. > > It is not a good practice. Please free such objects. > BTW, how many objects do you have in the list? Doesn't matter. No list should be able to grow without bounds in the kernel. -- James Morris <[EMAIL PROTECTED]>
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 3 Oct 2007, Tetsuo Handa wrote: > Regarding my singly-linked list, no entries are removed from the list. > It's append only (like CD-R media). I set is_deleted flag of a entry > instead of removing the entry from the list. Why so? This smells like a horrible leaking of memory. How fast can the list grow during the lifetime of the system? -- Jiri Kosina - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 2007-10-03 at 23:19 +0900, Tetsuo Handa wrote:
> Hello.
>
> Thank you for pointing out.
>
> Peter Zijlstra wrote:
> > > Currently, TOMOYO Linux avoids read_lock, on the assumption that
> > > (1) First, ptr->next is initialized with NULL.
> > > (2) Later, ptr->next is assigned non-NULL address.
> > > (3) Assigning to ptr->next is done atomically.
> > (4) wmb after asigning ptr->next
> > (5) rmb before reading ptr->next
> Excuse me, but I didn't understand why (4) and (5) are needed.
>
> append_function() {
>
> down(semaphore_for_write_protect);
> ...
> ptr = head;
> while (ptr->next) ptr = ptr->next;
> ptr->next = new_entry;
> ...
> up(semaphore_for_write_protect);
>
> }
If at all possible, use struct mutex.
> read_function() {
>
> for (ptr = head; ptr; ptr = ptr->next) {
> ...
> }
>
> }
>
> Are (4) and (5) needed even when (3) is exclusively protected by down() and
> up() ?
the up() would do 4. 5 ensures another cpu will actually see it. Althoug
in practise the various cache invalidations driven by the workload will
ensure it will become visible eventually anyway.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 2007-10-03 at 23:26 +0900, Tetsuo Handa wrote: > Peter Zijlstra wrote: > > Also, how do you avoid referencing dead data with your sll? I haven't > > actually looked at your patches, but the simple scheme you outlined > > didn't handle the iteration + concurrent removal scenario: > Regarding my singly-linked list, no entries are removed from the list. It's > append only (like CD-R media). > I set is_deleted flag of a entry instead of removing the entry from the list. sounds like a might fine memory leak / dos attack. - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
In article <[EMAIL PROTECTED]> (at Wed, 3 Oct 2007 23:26:57 +0900), Tetsuo Handa <[EMAIL PROTECTED]> says: > Peter Zijlstra wrote: > > Also, how do you avoid referencing dead data with your sll? I haven't > > actually looked at your patches, but the simple scheme you outlined > > didn't handle the iteration + concurrent removal scenario: > Regarding my singly-linked list, no entries are removed from the list. It's > append only (like CD-R media). > I set is_deleted flag of a entry instead of removing the entry from the list. It is not a good practice. Please free such objects. BTW, how many objects do you have in the list? --yoshfuji - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Peter Zijlstra wrote: > Also, how do you avoid referencing dead data with your sll? I haven't > actually looked at your patches, but the simple scheme you outlined > didn't handle the iteration + concurrent removal scenario: Regarding my singly-linked list, no entries are removed from the list. It's append only (like CD-R media). I set is_deleted flag of a entry instead of removing the entry from the list. Regards. - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
Thank you for pointing out.
Peter Zijlstra wrote:
> > Currently, TOMOYO Linux avoids read_lock, on the assumption that
> > (1) First, ptr->next is initialized with NULL.
> > (2) Later, ptr->next is assigned non-NULL address.
> > (3) Assigning to ptr->next is done atomically.
> (4) wmb after asigning ptr->next
> (5) rmb before reading ptr->next
Excuse me, but I didn't understand why (4) and (5) are needed.
append_function() {
down(semaphore_for_write_protect);
...
ptr = head;
while (ptr->next) ptr = ptr->next;
ptr->next = new_entry;
...
up(semaphore_for_write_protect);
}
read_function() {
for (ptr = head; ptr; ptr = ptr->next) {
...
}
}
Are (4) and (5) needed even when (3) is exclusively protected by down() and
up() ?
Regards.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 2007-10-03 at 22:59 +0900, Tetsuo Handa wrote:
> Hello.
>
> KaiGai Kohei wrote:
> > If so, you can apply RCU instead to avoid read lock
> > when scanning the list, like:
> >
> > rcu_read_lock();
> > list_for_each_entry(...) {
> >
> > }
> > rcu_read_unlock();
>
> Can I sleep between rcu_read_lock() and rcu_read_unlock() ?
> As far as I saw, rcu_read_lock() makes in_atomic() true, so I think I can't
> sleep.
>
> If I use RCU, I have to give up " [TOMOYO 13/15] Conditional permission
> support"
> because tmy_check_condition() can sleep.
You can indeed not sleep in an rcu_read_lock() section. However, you
could grab a reference on an item, stop the iteration, drop
rcu_read_lock. Do you thing, re-acquire rcu_read_lock(), drop the ref,
and continue the iteration.
Also, how do you avoid referencing dead data with your sll? I haven't
actually looked at your patches, but the simple scheme you outlined
didn't handle the iteration + concurrent removal scenario:
thread 1 thread 2
foo = ptr->next
< schedule >
killme = ptr->next (same item)
ptr->next = ptr->next->next;
kfree(killme)
< schedule >
foo->bar <-- *BANG*
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
KaiGai Kohei wrote:
> If so, you can apply RCU instead to avoid read lock
> when scanning the list, like:
>
> rcu_read_lock();
> list_for_each_entry(...) {
>
> }
> rcu_read_unlock();
Can I sleep between rcu_read_lock() and rcu_read_unlock() ?
As far as I saw, rcu_read_lock() makes in_atomic() true, so I think I can't
sleep.
If I use RCU, I have to give up " [TOMOYO 13/15] Conditional permission support"
because tmy_check_condition() can sleep.
Regards.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Tetsuo Handa wrote:
James Morris wrote:
I'm pretty sure that the singly linked list idea has been rejected a few
times. Just use the existing API.
Too bad...
Well, is there a way to avoid read_lock when reading list?
Currently, TOMOYO Linux avoids read_lock, on the assumption that
(1) First, ptr->next is initialized with NULL.
(2) Later, ptr->next is assigned non-NULL address.
(3) Assigning to ptr->next is done atomically.
Regards.
Is it all of the purpose for the list structure?
If so, you can apply RCU instead to avoid read lock
when scanning the list, like:
rcu_read_lock();
list_for_each_entry(...) {
}
rcu_read_unlock();
--
KaiGai Kohei <[EMAIL PROTECTED]>
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 2007-10-03 at 22:04 +0900, Tetsuo Handa wrote: > James Morris wrote: > > I'm pretty sure that the singly linked list idea has been rejected a few > > times. Just use the existing API. > Too bad... > > Well, is there a way to avoid read_lock when reading list? > > Currently, TOMOYO Linux avoids read_lock, on the assumption that > (1) First, ptr->next is initialized with NULL. > (2) Later, ptr->next is assigned non-NULL address. > (3) Assigning to ptr->next is done atomically. (4) wmb after asigning ptr->next (5) rmb before reading ptr->next But please do look at the various rcu list primitives. RCU allows one to avoid non-exclusive locks in many cases. non-exclusive locks are evil, they must all die... - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
In article <[EMAIL PROTECTED]> (at Wed, 3 Oct 2007 22:04:11 +0900), Tetsuo Handa <[EMAIL PROTECTED]> says: > Well, is there a way to avoid read_lock when reading list? > > Currently, TOMOYO Linux avoids read_lock, on the assumption that > (1) First, ptr->next is initialized with NULL. > (2) Later, ptr->next is assigned non-NULL address. > (3) Assigning to ptr->next is done atomically. RCU? --yoshfuji - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
James Morris wrote: > I'm pretty sure that the singly linked list idea has been rejected a few > times. Just use the existing API. Too bad... Well, is there a way to avoid read_lock when reading list? Currently, TOMOYO Linux avoids read_lock, on the assumption that (1) First, ptr->next is initialized with NULL. (2) Later, ptr->next is assigned non-NULL address. (3) Assigning to ptr->next is done atomically. Regards. - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 3 Oct 2007, YOSHIFUJI Hideaki / µÈÆ£±ÑÌÀ wrote: > In article <[EMAIL PROTECTED]> (at Wed, 3 Oct 2007 20:24:52 +0900), Tetsuo > Handa <[EMAIL PROTECTED]> says: > > > It seems that standard kernel list API does not have singly-linked list > > manipulation. > > I'm considering the following list manipulation API. > > Tstsuo, please name it "slist", which is well-known. I'm pretty sure that the singly linked list idea has been rejected a few times. Just use the existing API. -- James Morris <[EMAIL PROTECTED]>
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
In article <[EMAIL PROTECTED]> (at Wed, 3 Oct 2007 20:24:52 +0900), Tetsuo Handa <[EMAIL PROTECTED]> says: > It seems that standard kernel list API does not have singly-linked list > manipulation. > I'm considering the following list manipulation API. Tstsuo, please name it "slist", which is well-known. --yoshfuji - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
YOSHIFUJI Hideaki wrote:
> Introducing your own list is not good.
> Please use hlist or introduce new "slist".
James Morris wrote:
> You're introducing a custom API, which is open-coded repeatedly throughout
> your module.
>
> All linked lists (at least, new ones) must use the standard kernel list
> API.
It seems that standard kernel list API does not have singly-linked list
manipulation.
I'm considering the following list manipulation API.
--- Start of code ---
#include
#include
static inline void prefetch(const void *x) {;}
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ const typeof( ((type *)0)->member )
*__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );})
/*
* nphlist -- hlist with no pointer to previous
*/
struct nphlist_node {
struct nphlist_node *next;
};
struct nphlist_head {
struct nphlist_node *first;
};
#define NPHLIST_HEAD_INIT { .first = NULL }
#define NPHLIST_HEAD(name) struct nphlist_head name = NPHLIST_HEAD_INIT
#define INIT_NPHLIST_HEAD(ptr) ((ptr)->first = NULL)
#define INIT_NPHLIST_NODE(ptr) ((ptr)->next = NULL)
static inline void nphlist_add(struct nphlist_node *entry, struct nphlist_head
*list) {
struct nphlist_node *ptr = list->first;
if (ptr) {
while (ptr->next)
ptr = ptr->next;
ptr->next = entry;
} else {
list->first = entry;
}
}
#define nphlist_entry(ptr, type, member) container_of(ptr,type,member)
/**
* nphlist_for_each_entry - iterate over list of given type
* @tpos: the type * to use as a loop cursor.
* @pos:the nph_list to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the nphlist_node within the struct.
*/
#define nphlist_for_each_entry(tpos, pos, head, member) \
for (pos = (head); \
pos && ({ prefetch(pos->next); 1;}) && \
({ tpos = nphlist_entry(pos, typeof(*tpos), member); 1;});
\
pos = pos->next)
struct something {
struct nphlist_node next;
int v;
};
static NPHLIST_HEAD(data);
int main(int argc, char *argv[]) {
struct something *ptr;
struct nphlist_node *p;
int i;
for (i = 0; i < 10; i++) {
printf("add %d\n", i);
ptr = malloc(sizeof(*ptr));
INIT_NPHLIST_NODE(&(ptr->next));
ptr->v = 10 + i;
nphlist_add(&(ptr->next), );
}
printf("dump\n");
nphlist_for_each_entry(ptr, p, data.first, next) {
printf("%d\n", ptr->v);
}
return 0;
}
--- End of code ---
Where should I put this API, in include/linux/list.h or
security/tomoyo/include/tomoyo.h ?
If I should put in include/linux/list.h , what name would be appropriate?
May I name it "slist" instead of "nphlist" ?
Regards.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
YOSHIFUJI Hideaki wrote:
Introducing your own list is not good.
Please use hlist or introduce new slist.
James Morris wrote:
You're introducing a custom API, which is open-coded repeatedly throughout
your module.
All linked lists (at least, new ones) must use the standard kernel list
API.
It seems that standard kernel list API does not have singly-linked list
manipulation.
I'm considering the following list manipulation API.
--- Start of code ---
#include stdio.h
#include stdlib.h
static inline void prefetch(const void *x) {;}
#define offsetof(TYPE, MEMBER) ((size_t) ((TYPE *)0)-MEMBER)
#define container_of(ptr, type, member) ({ const typeof( ((type *)0)-member )
*__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );})
/*
* nphlist -- hlist with no pointer to previous
*/
struct nphlist_node {
struct nphlist_node *next;
};
struct nphlist_head {
struct nphlist_node *first;
};
#define NPHLIST_HEAD_INIT { .first = NULL }
#define NPHLIST_HEAD(name) struct nphlist_head name = NPHLIST_HEAD_INIT
#define INIT_NPHLIST_HEAD(ptr) ((ptr)-first = NULL)
#define INIT_NPHLIST_NODE(ptr) ((ptr)-next = NULL)
static inline void nphlist_add(struct nphlist_node *entry, struct nphlist_head
*list) {
struct nphlist_node *ptr = list-first;
if (ptr) {
while (ptr-next)
ptr = ptr-next;
ptr-next = entry;
} else {
list-first = entry;
}
}
#define nphlist_entry(ptr, type, member) container_of(ptr,type,member)
/**
* nphlist_for_each_entry - iterate over list of given type
* @tpos: the type * to use as a loop cursor.
* @pos:the struct nph_list to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the nphlist_node within the struct.
*/
#define nphlist_for_each_entry(tpos, pos, head, member) \
for (pos = (head); \
pos ({ prefetch(pos-next); 1;}) \
({ tpos = nphlist_entry(pos, typeof(*tpos), member); 1;});
\
pos = pos-next)
struct something {
struct nphlist_node next;
int v;
};
static NPHLIST_HEAD(data);
int main(int argc, char *argv[]) {
struct something *ptr;
struct nphlist_node *p;
int i;
for (i = 0; i 10; i++) {
printf(add %d\n, i);
ptr = malloc(sizeof(*ptr));
INIT_NPHLIST_NODE((ptr-next));
ptr-v = 10 + i;
nphlist_add((ptr-next), data);
}
printf(dump\n);
nphlist_for_each_entry(ptr, p, data.first, next) {
printf(%d\n, ptr-v);
}
return 0;
}
--- End of code ---
Where should I put this API, in include/linux/list.h or
security/tomoyo/include/tomoyo.h ?
If I should put in include/linux/list.h , what name would be appropriate?
May I name it slist instead of nphlist ?
Regards.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
In article [EMAIL PROTECTED] (at Wed, 3 Oct 2007 20:24:52 +0900), Tetsuo Handa [EMAIL PROTECTED] says: It seems that standard kernel list API does not have singly-linked list manipulation. I'm considering the following list manipulation API. Tstsuo, please name it slist, which is well-known. --yoshfuji - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 3 Oct 2007, YOSHIFUJI Hideaki / µÈÆ£±ÑÌÀ wrote: In article [EMAIL PROTECTED] (at Wed, 3 Oct 2007 20:24:52 +0900), Tetsuo Handa [EMAIL PROTECTED] says: It seems that standard kernel list API does not have singly-linked list manipulation. I'm considering the following list manipulation API. Tstsuo, please name it slist, which is well-known. I'm pretty sure that the singly linked list idea has been rejected a few times. Just use the existing API. -- James Morris [EMAIL PROTECTED]
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
In article [EMAIL PROTECTED] (at Wed, 3 Oct 2007 22:04:11 +0900), Tetsuo Handa [EMAIL PROTECTED] says: Well, is there a way to avoid read_lock when reading list? Currently, TOMOYO Linux avoids read_lock, on the assumption that (1) First, ptr-next is initialized with NULL. (2) Later, ptr-next is assigned non-NULL address. (3) Assigning to ptr-next is done atomically. RCU? --yoshfuji - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
James Morris wrote: I'm pretty sure that the singly linked list idea has been rejected a few times. Just use the existing API. Too bad... Well, is there a way to avoid read_lock when reading list? Currently, TOMOYO Linux avoids read_lock, on the assumption that (1) First, ptr-next is initialized with NULL. (2) Later, ptr-next is assigned non-NULL address. (3) Assigning to ptr-next is done atomically. Regards. - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 2007-10-03 at 22:04 +0900, Tetsuo Handa wrote: James Morris wrote: I'm pretty sure that the singly linked list idea has been rejected a few times. Just use the existing API. Too bad... Well, is there a way to avoid read_lock when reading list? Currently, TOMOYO Linux avoids read_lock, on the assumption that (1) First, ptr-next is initialized with NULL. (2) Later, ptr-next is assigned non-NULL address. (3) Assigning to ptr-next is done atomically. (4) wmb after asigning ptr-next (5) rmb before reading ptr-next But please do look at the various rcu list primitives. RCU allows one to avoid non-exclusive locks in many cases. non-exclusive locks are evil, they must all die... - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Tetsuo Handa wrote:
James Morris wrote:
I'm pretty sure that the singly linked list idea has been rejected a few
times. Just use the existing API.
Too bad...
Well, is there a way to avoid read_lock when reading list?
Currently, TOMOYO Linux avoids read_lock, on the assumption that
(1) First, ptr-next is initialized with NULL.
(2) Later, ptr-next is assigned non-NULL address.
(3) Assigning to ptr-next is done atomically.
Regards.
Is it all of the purpose for the list structure?
If so, you can apply RCU instead to avoid read lock
when scanning the list, like:
rcu_read_lock();
list_for_each_entry(...) {
}
rcu_read_unlock();
--
KaiGai Kohei [EMAIL PROTECTED]
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 2007-10-03 at 22:59 +0900, Tetsuo Handa wrote:
Hello.
KaiGai Kohei wrote:
If so, you can apply RCU instead to avoid read lock
when scanning the list, like:
rcu_read_lock();
list_for_each_entry(...) {
}
rcu_read_unlock();
Can I sleep between rcu_read_lock() and rcu_read_unlock() ?
As far as I saw, rcu_read_lock() makes in_atomic() true, so I think I can't
sleep.
If I use RCU, I have to give up [TOMOYO 13/15] Conditional permission
support
because tmy_check_condition() can sleep.
You can indeed not sleep in an rcu_read_lock() section. However, you
could grab a reference on an item, stop the iteration, drop
rcu_read_lock. Do you thing, re-acquire rcu_read_lock(), drop the ref,
and continue the iteration.
Also, how do you avoid referencing dead data with your sll? I haven't
actually looked at your patches, but the simple scheme you outlined
didn't handle the iteration + concurrent removal scenario:
thread 1 thread 2
foo = ptr-next
schedule
killme = ptr-next (same item)
ptr-next = ptr-next-next;
kfree(killme)
schedule
foo-bar -- *BANG*
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
Thank you for pointing out.
Peter Zijlstra wrote:
Currently, TOMOYO Linux avoids read_lock, on the assumption that
(1) First, ptr-next is initialized with NULL.
(2) Later, ptr-next is assigned non-NULL address.
(3) Assigning to ptr-next is done atomically.
(4) wmb after asigning ptr-next
(5) rmb before reading ptr-next
Excuse me, but I didn't understand why (4) and (5) are needed.
append_function() {
down(semaphore_for_write_protect);
...
ptr = head;
while (ptr-next) ptr = ptr-next;
ptr-next = new_entry;
...
up(semaphore_for_write_protect);
}
read_function() {
for (ptr = head; ptr; ptr = ptr-next) {
...
}
}
Are (4) and (5) needed even when (3) is exclusively protected by down() and
up() ?
Regards.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
KaiGai Kohei wrote:
If so, you can apply RCU instead to avoid read lock
when scanning the list, like:
rcu_read_lock();
list_for_each_entry(...) {
}
rcu_read_unlock();
Can I sleep between rcu_read_lock() and rcu_read_unlock() ?
As far as I saw, rcu_read_lock() makes in_atomic() true, so I think I can't
sleep.
If I use RCU, I have to give up [TOMOYO 13/15] Conditional permission support
because tmy_check_condition() can sleep.
Regards.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Peter Zijlstra wrote: Also, how do you avoid referencing dead data with your sll? I haven't actually looked at your patches, but the simple scheme you outlined didn't handle the iteration + concurrent removal scenario: Regarding my singly-linked list, no entries are removed from the list. It's append only (like CD-R media). I set is_deleted flag of a entry instead of removing the entry from the list. Regards. - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
In article [EMAIL PROTECTED] (at Wed, 3 Oct 2007 23:26:57 +0900), Tetsuo Handa [EMAIL PROTECTED] says: Peter Zijlstra wrote: Also, how do you avoid referencing dead data with your sll? I haven't actually looked at your patches, but the simple scheme you outlined didn't handle the iteration + concurrent removal scenario: Regarding my singly-linked list, no entries are removed from the list. It's append only (like CD-R media). I set is_deleted flag of a entry instead of removing the entry from the list. It is not a good practice. Please free such objects. BTW, how many objects do you have in the list? --yoshfuji - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 2007-10-03 at 23:26 +0900, Tetsuo Handa wrote: Peter Zijlstra wrote: Also, how do you avoid referencing dead data with your sll? I haven't actually looked at your patches, but the simple scheme you outlined didn't handle the iteration + concurrent removal scenario: Regarding my singly-linked list, no entries are removed from the list. It's append only (like CD-R media). I set is_deleted flag of a entry instead of removing the entry from the list. sounds like a might fine memory leak / dos attack. - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 2007-10-03 at 23:19 +0900, Tetsuo Handa wrote:
Hello.
Thank you for pointing out.
Peter Zijlstra wrote:
Currently, TOMOYO Linux avoids read_lock, on the assumption that
(1) First, ptr-next is initialized with NULL.
(2) Later, ptr-next is assigned non-NULL address.
(3) Assigning to ptr-next is done atomically.
(4) wmb after asigning ptr-next
(5) rmb before reading ptr-next
Excuse me, but I didn't understand why (4) and (5) are needed.
append_function() {
down(semaphore_for_write_protect);
...
ptr = head;
while (ptr-next) ptr = ptr-next;
ptr-next = new_entry;
...
up(semaphore_for_write_protect);
}
If at all possible, use struct mutex.
read_function() {
for (ptr = head; ptr; ptr = ptr-next) {
...
}
}
Are (4) and (5) needed even when (3) is exclusively protected by down() and
up() ?
the up() would do 4. 5 ensures another cpu will actually see it. Althoug
in practise the various cache invalidations driven by the workload will
ensure it will become visible eventually anyway.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 3 Oct 2007, Tetsuo Handa wrote: Regarding my singly-linked list, no entries are removed from the list. It's append only (like CD-R media). I set is_deleted flag of a entry instead of removing the entry from the list. Why so? This smells like a horrible leaking of memory. How fast can the list grow during the lifetime of the system? -- Jiri Kosina - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 3 Oct 2007, YOSHIFUJI Hideaki / µÈÆ£±ÑÌÀ wrote: In article [EMAIL PROTECTED] (at Wed, 3 Oct 2007 23:26:57 +0900), Tetsuo Handa [EMAIL PROTECTED] says: Peter Zijlstra wrote: Also, how do you avoid referencing dead data with your sll? I haven't actually looked at your patches, but the simple scheme you outlined didn't handle the iteration + concurrent removal scenario: Regarding my singly-linked list, no entries are removed from the list. It's append only (like CD-R media). I set is_deleted flag of a entry instead of removing the entry from the list. It is not a good practice. Please free such objects. BTW, how many objects do you have in the list? Doesn't matter. No list should be able to grow without bounds in the kernel. -- James Morris [EMAIL PROTECTED]
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Wed, 2007-10-03 at 23:19 +0900, Tetsuo Handa wrote:
Hello.
Thank you for pointing out.
Peter Zijlstra wrote:
Currently, TOMOYO Linux avoids read_lock, on the assumption that
(1) First, ptr-next is initialized with NULL.
(2) Later, ptr-next is assigned non-NULL address.
(3) Assigning to ptr-next is done atomically.
(4) wmb after asigning ptr-next
(5) rmb before reading ptr-next
Excuse me, but I didn't understand why (4) and (5) are needed.
append_function() {
down(semaphore_for_write_protect);
...
ptr = head;
while (ptr-next) ptr = ptr-next;
ptr-next = new_entry;
...
up(semaphore_for_write_protect);
}
It seems to me that this function alone is a reason to argue against
using a singly linked list. I know your patch doesn't actually contain
this as a function but it does use the same logic to append to your
lists. Does the overhead of the second pointer that the regular list
head uses outweigh the O(1) insertion and deletion it provides
(especially in your case)? I know domain transitions are rare but why
use something with O(N) insertion? This could be one reason why there
isn't an slist already in list.h
Dave Quigley
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello. YOSHIFUJI Hideaki wrote: It is not a good practice. Please free such objects. BTW, how many objects do you have in the list? It varies from 0 to some thousands, depending on the policy supplied by the administrator and/or the policy appended by learning mode. Peter Zijlstra wrote: sounds like a might fine memory leak / dos attack. TOMOYO Linux keeps the policy in CD-R's manner. Thus, once an entry is written, it's pointer is valid forever. TOMOYO Linux's simplicity (singly-linked list with no read_lock) comes from this keep the policy in CD-R's manner. Yes, it is a kind of memory leak, but is controllable. The kernel no longer requires memory after entering into enforcing mode. So, attackers can't do DoS attack after entering into enforcing mode. Regards. - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
James Morris <[EMAIL PROTECTED]> writes: > > All linked lists (at least, new ones) must use the standard kernel list > API. Really? Why? That rule is new to me. Would also seem very limiting especially since the standard kernel lists do not allow to express important patterns (like single linked lists) I don't think that is a requirement. -Andi - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Tue, 2 Oct 2007, Tetsuo Handa wrote:
> Hello.
>
> Thank you for your comment.
>
> James Morris wrote:
> > Why do you need to avoid spinlocks for these manipulations?
>
> I don't need to use spinlocks here.
> What I need to do here is avoid read/write reordering,
> so mb() will be appropriate here.
>
> struct something {
> struct something *next;
> void *data;
> };
>
> struct something *prev_ptr = ...;
> struct something *new_ptr = kmalloc(sizeof(*new_ptr), GFP_KERNEL);
> new_ptr->next = NULL;
> new_ptr->data = some_value;
> mb();
> prev_ptr->next = new_ptr;
You're introducing a custom API, which is open-coded repeatedly throughout
your module.
All linked lists (at least, new ones) must use the standard kernel list
API.
> Performance is not critical because this mb() is called
> only when appending new entry to the singly-linked list.
Most of these uses appear to be slow path or nested inside other locks,
while overall, performance is likely to be dominated by your string
matching and permission checking. Use of mb(), which is typically
considered less understandable, in this case does not appear to be
justified vs. normal locking, and you also need to use the standard list
API. If performance really is an issue, then consider RCU.
- James
--
James Morris
<[EMAIL PROTECTED]>
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
In article <[EMAIL PROTECTED]> (at Tue, 2 Oct 2007 21:44:57 +0900), Tetsuo Handa <[EMAIL PROTECTED]> says: > If I use "struct hlist_node" which has two pointers, > it needs more memory than "struct something" which has one pointer. > It is possible to use API defined in include/linux/list.h , > but to reduce memory usage, I dare not use these API. > Singly-linked list's rule in TOMOYO Linux is quite simple, > "ptr->next is NULL if the last element" and "non-NULL if not". Introducing your own list is not good. Please use hlist or introduce new "slist". --yoshfuji - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
Thank you for your comment.
James Morris wrote:
> Why do you need to avoid spinlocks for these manipulations?
I don't need to use spinlocks here.
What I need to do here is avoid read/write reordering,
so mb() will be appropriate here.
struct something {
struct something *next;
void *data;
};
struct something *prev_ptr = ...;
struct something *new_ptr = kmalloc(sizeof(*new_ptr), GFP_KERNEL);
new_ptr->next = NULL;
new_ptr->data = some_value;
mb();
prev_ptr->next = new_ptr;
TOMOYO Linux doesn't use locks for reading singly-linked list.
Thus, new_ptr->data has to be made visible to other CPUs
before new_ptr is appended at the tail of singly-linked list.
Otherwise, other CPU may read undefined new_ptr->data values.
Performance is not critical because this mb() is called
only when appending new entry to the singly-linked list.
> Please use standard kernel list handling, per include/linux/list.h
Since new_ptr never be removed, new_ptr needn't to know
it's previous element's address, thus having only ->next pointer is enough.
new_ptr->next is assigned *only once*
(initialized with NULL, and assigned non-NULL later),
indicating "if ptr->next == NULL, ptr is the last element" and
"if ptr->next != NULL, ptr is not the last element".
If I use "struct hlist_node" which has two pointers,
it needs more memory than "struct something" which has one pointer.
It is possible to use API defined in include/linux/list.h ,
but to reduce memory usage, I dare not use these API.
Singly-linked list's rule in TOMOYO Linux is quite simple,
"ptr->next is NULL if the last element" and "non-NULL if not".
Regards.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Tue, 2 Oct 2007, Kentaro Takeda wrote:
> +
> + mb(); /* Instead of using spinlock. */
> + ptr = domain_initializer_list;
> + if (ptr) {
> + while (ptr->next)
> + ptr = ptr->next;
> + ptr->next = new_entry;
> + } else
> + domain_initializer_list = new_entry;
> +
Please use standard kernel list handling, per include/linux/list.h
Why do you need to avoid spinlocks for these manipulations?
- James
--
James Morris
<[EMAIL PROTECTED]>
-
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/
[TOMOYO 05/15](repost) Domain transition handler functions.
Domain transition functions for TOMOYO Linux.
Every process belongs to a domain in TOMOYO Linux.
Domain transition occurs when execve(2) is called
and the domain is expressed as 'process invocation history',
such as ' /sbin/init /etc/init.d/rc'.
Domain information is stored in task_struct->security.
Signed-off-by: Kentaro Takeda <[EMAIL PROTECTED]>
Signed-off-by: Tetsuo Handa <[EMAIL PROTECTED]>
---
security/tomoyo/domain.c | 1256 +++
1 files changed, 1256 insertions(+)
--- /dev/null 1970-01-01 00:00:00.0 +
+++ linux-2.6/security/tomoyo/domain.c 2007-10-02 11:26:21.0 +0900
@@ -0,0 +1,1256 @@
+/*
+ * security/tomoyo/domain.c
+ *
+ * Domain transition functions for TOMOYO Linux.
+ */
+
+#include "tomoyo.h"
+#include "realpath.h"
+#include
+#include
+
+/* VARIABLES */
+
+/* Lock for appending domain's ACL. */
+DECLARE_MUTEX(domain_acl_lock);
+
+/* Domain creation lock. */
+static DECLARE_MUTEX(new_domain_assign_lock);
+
+/* The structure for program files to force domain reconstruction. */
+
+struct domain_initializer_entry {
+ struct domain_initializer_entry *next;
+ const struct path_info *domainname;/* This may be NULL */
+ const struct path_info *program;
+ u8 is_deleted;
+ u8 is_not;
+ u8 is_last_name;
+};
+
+/* The structure for domains to not to transit domains. */
+
+struct domain_keeper_entry {
+ struct domain_keeper_entry *next;
+ const struct path_info *domainname;
+ const struct path_info *program; /* This may be NULL */
+ u8 is_deleted;
+ u8 is_not;
+ u8 is_last_name;
+};
+
+/* The structure for program files that should be aggregated. */
+
+struct aggregator_entry {
+ struct aggregator_entry *next;
+ const struct path_info *original_name;
+ const struct path_info *aggregated_name;
+ u8 is_deleted;
+};
+
+/* The structure for program files that should be aliased. */
+
+struct alias_entry {
+ struct alias_entry *next;
+ const struct path_info *original_name;
+ const struct path_info *aliased_name;
+ u8 is_deleted;
+};
+
+/* UTILITY FUNCTIONS */
+
+/**
+ * tmy_is_domain_def - check if the line is likely a domain definition.
+ * @buffer: the line to check.
+ *
+ * Returns nonzero if @buffer is likely a domain definition.
+ * Returns zero otherwise.
+ *
+ * For complete validation check, use tmy_is_correct_domain().
+ */
+int tmy_is_domain_def(const unsigned char *buffer)
+{
+ return strncmp(buffer, TMY_ROOT_NAME, TMY_ROOT_NAME_LEN) == 0;
+}
+
+/**
+ * tmy_add_acl - add an entry to a domain.
+ * @ptr: pointer to the last "struct acl_info" of @domain. May be NULL.
+ * @domain: pointer to "struct domain_info".
+ * @new_ptr: pointer to "struct acl_info" to add.
+ *
+ * Returns zero.
+ *
+ * To be honest, I can calculate @ptr from @domain.
+ * But since the caller knows @ptr, I use it.
+ */
+int tmy_add_acl(struct acl_info *ptr,
+ struct domain_info *domain,
+ struct acl_info *new_ptr)
+{
+ mb(); /* Instead of using spinlock. */
+
+ if (!ptr)
+ domain->first_acl_ptr = (struct acl_info *) new_ptr;
+ else
+ ptr->next = (struct acl_info *) new_ptr;
+
+ tmy_update_counter(TMY_UPDATE_DOMAINPOLICY);
+ return 0;
+}
+
+/**
+ * tmy_del_acl - remove an entry from a domain
+ * @ptr: pointer to "struct acl_info" to remove.
+ *
+ * Returns zero.
+ *
+ * TOMOYO Linux doesn't free memory used by policy because policies are not
+ * so frequently changed after entring into enforcing mode.
+ * This makes the code free of read-lock.
+ * The caller uses "down(_acl_lock);" as write-lock.
+ */
+int tmy_del_acl(struct acl_info *ptr)
+{
+ ptr->is_deleted = 1;
+ tmy_update_counter(TMY_UPDATE_DOMAINPOLICY);
+ return 0;
+}
+
+/ DOMAIN INITIALIZER HANDLER
/
+
+static struct domain_initializer_entry *domain_initializer_list;
+
+/* Update domain initializer list. */
+static int tmy_add_domain_initializer_entry(const char *domainname,
+ const char *program,
+ const u8 is_not,
+ const u8 is_delete)
+{
+ struct domain_initializer_entry *new_entry;
+ struct domain_initializer_entry *ptr;
+ static DECLARE_MUTEX(lock);
+ const struct path_info *saved_program;
+ const struct path_info *saved_domainname = NULL;
+ int error = -ENOMEM;
+ u8 is_last_name = 0;
+
+ if (!tmy_correct_path(program, 1, -1, -1, __FUNCTION__))
+ return -EINVAL; /* No patterns allowed. */
+
+ if (domainname) {
+ if (!tmy_is_domain_def(domainname) &&
+
[TOMOYO 05/15](repost) Domain transition handler functions.
Domain transition functions for TOMOYO Linux.
Every process belongs to a domain in TOMOYO Linux.
Domain transition occurs when execve(2) is called
and the domain is expressed as 'process invocation history',
such as 'kernel /sbin/init /etc/init.d/rc'.
Domain information is stored in task_struct-security.
Signed-off-by: Kentaro Takeda [EMAIL PROTECTED]
Signed-off-by: Tetsuo Handa [EMAIL PROTECTED]
---
security/tomoyo/domain.c | 1256 +++
1 files changed, 1256 insertions(+)
--- /dev/null 1970-01-01 00:00:00.0 +
+++ linux-2.6/security/tomoyo/domain.c 2007-10-02 11:26:21.0 +0900
@@ -0,0 +1,1256 @@
+/*
+ * security/tomoyo/domain.c
+ *
+ * Domain transition functions for TOMOYO Linux.
+ */
+
+#include tomoyo.h
+#include realpath.h
+#include linux/highmem.h
+#include linux/binfmts.h
+
+/* VARIABLES */
+
+/* Lock for appending domain's ACL. */
+DECLARE_MUTEX(domain_acl_lock);
+
+/* Domain creation lock. */
+static DECLARE_MUTEX(new_domain_assign_lock);
+
+/* The structure for program files to force domain reconstruction. */
+
+struct domain_initializer_entry {
+ struct domain_initializer_entry *next;
+ const struct path_info *domainname;/* This may be NULL */
+ const struct path_info *program;
+ u8 is_deleted;
+ u8 is_not;
+ u8 is_last_name;
+};
+
+/* The structure for domains to not to transit domains. */
+
+struct domain_keeper_entry {
+ struct domain_keeper_entry *next;
+ const struct path_info *domainname;
+ const struct path_info *program; /* This may be NULL */
+ u8 is_deleted;
+ u8 is_not;
+ u8 is_last_name;
+};
+
+/* The structure for program files that should be aggregated. */
+
+struct aggregator_entry {
+ struct aggregator_entry *next;
+ const struct path_info *original_name;
+ const struct path_info *aggregated_name;
+ u8 is_deleted;
+};
+
+/* The structure for program files that should be aliased. */
+
+struct alias_entry {
+ struct alias_entry *next;
+ const struct path_info *original_name;
+ const struct path_info *aliased_name;
+ u8 is_deleted;
+};
+
+/* UTILITY FUNCTIONS */
+
+/**
+ * tmy_is_domain_def - check if the line is likely a domain definition.
+ * @buffer: the line to check.
+ *
+ * Returns nonzero if @buffer is likely a domain definition.
+ * Returns zero otherwise.
+ *
+ * For complete validation check, use tmy_is_correct_domain().
+ */
+int tmy_is_domain_def(const unsigned char *buffer)
+{
+ return strncmp(buffer, TMY_ROOT_NAME, TMY_ROOT_NAME_LEN) == 0;
+}
+
+/**
+ * tmy_add_acl - add an entry to a domain.
+ * @ptr: pointer to the last struct acl_info of @domain. May be NULL.
+ * @domain: pointer to struct domain_info.
+ * @new_ptr: pointer to struct acl_info to add.
+ *
+ * Returns zero.
+ *
+ * To be honest, I can calculate @ptr from @domain.
+ * But since the caller knows @ptr, I use it.
+ */
+int tmy_add_acl(struct acl_info *ptr,
+ struct domain_info *domain,
+ struct acl_info *new_ptr)
+{
+ mb(); /* Instead of using spinlock. */
+
+ if (!ptr)
+ domain-first_acl_ptr = (struct acl_info *) new_ptr;
+ else
+ ptr-next = (struct acl_info *) new_ptr;
+
+ tmy_update_counter(TMY_UPDATE_DOMAINPOLICY);
+ return 0;
+}
+
+/**
+ * tmy_del_acl - remove an entry from a domain
+ * @ptr: pointer to struct acl_info to remove.
+ *
+ * Returns zero.
+ *
+ * TOMOYO Linux doesn't free memory used by policy because policies are not
+ * so frequently changed after entring into enforcing mode.
+ * This makes the code free of read-lock.
+ * The caller uses down(domain_acl_lock); as write-lock.
+ */
+int tmy_del_acl(struct acl_info *ptr)
+{
+ ptr-is_deleted = 1;
+ tmy_update_counter(TMY_UPDATE_DOMAINPOLICY);
+ return 0;
+}
+
+/ DOMAIN INITIALIZER HANDLER
/
+
+static struct domain_initializer_entry *domain_initializer_list;
+
+/* Update domain initializer list. */
+static int tmy_add_domain_initializer_entry(const char *domainname,
+ const char *program,
+ const u8 is_not,
+ const u8 is_delete)
+{
+ struct domain_initializer_entry *new_entry;
+ struct domain_initializer_entry *ptr;
+ static DECLARE_MUTEX(lock);
+ const struct path_info *saved_program;
+ const struct path_info *saved_domainname = NULL;
+ int error = -ENOMEM;
+ u8 is_last_name = 0;
+
+ if (!tmy_correct_path(program, 1, -1, -1, __FUNCTION__))
+ return -EINVAL; /* No patterns allowed. */
+
+ if (domainname) {
+ if (!tmy_is_domain_def(domainname)
+
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Tue, 2 Oct 2007, Kentaro Takeda wrote:
+
+ mb(); /* Instead of using spinlock. */
+ ptr = domain_initializer_list;
+ if (ptr) {
+ while (ptr-next)
+ ptr = ptr-next;
+ ptr-next = new_entry;
+ } else
+ domain_initializer_list = new_entry;
+
Please use standard kernel list handling, per include/linux/list.h
Why do you need to avoid spinlocks for these manipulations?
- James
--
James Morris
[EMAIL PROTECTED]
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
Hello.
Thank you for your comment.
James Morris wrote:
Why do you need to avoid spinlocks for these manipulations?
I don't need to use spinlocks here.
What I need to do here is avoid read/write reordering,
so mb() will be appropriate here.
struct something {
struct something *next;
void *data;
};
struct something *prev_ptr = ...;
struct something *new_ptr = kmalloc(sizeof(*new_ptr), GFP_KERNEL);
new_ptr-next = NULL;
new_ptr-data = some_value;
mb();
prev_ptr-next = new_ptr;
TOMOYO Linux doesn't use locks for reading singly-linked list.
Thus, new_ptr-data has to be made visible to other CPUs
before new_ptr is appended at the tail of singly-linked list.
Otherwise, other CPU may read undefined new_ptr-data values.
Performance is not critical because this mb() is called
only when appending new entry to the singly-linked list.
Please use standard kernel list handling, per include/linux/list.h
Since new_ptr never be removed, new_ptr needn't to know
it's previous element's address, thus having only -next pointer is enough.
new_ptr-next is assigned *only once*
(initialized with NULL, and assigned non-NULL later),
indicating if ptr-next == NULL, ptr is the last element and
if ptr-next != NULL, ptr is not the last element.
If I use struct hlist_node which has two pointers,
it needs more memory than struct something which has one pointer.
It is possible to use API defined in include/linux/list.h ,
but to reduce memory usage, I dare not use these API.
Singly-linked list's rule in TOMOYO Linux is quite simple,
ptr-next is NULL if the last element and non-NULL if not.
Regards.
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
In article [EMAIL PROTECTED] (at Tue, 2 Oct 2007 21:44:57 +0900), Tetsuo Handa [EMAIL PROTECTED] says: If I use struct hlist_node which has two pointers, it needs more memory than struct something which has one pointer. It is possible to use API defined in include/linux/list.h , but to reduce memory usage, I dare not use these API. Singly-linked list's rule in TOMOYO Linux is quite simple, ptr-next is NULL if the last element and non-NULL if not. Introducing your own list is not good. Please use hlist or introduce new slist. --yoshfuji - 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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
On Tue, 2 Oct 2007, Tetsuo Handa wrote:
Hello.
Thank you for your comment.
James Morris wrote:
Why do you need to avoid spinlocks for these manipulations?
I don't need to use spinlocks here.
What I need to do here is avoid read/write reordering,
so mb() will be appropriate here.
struct something {
struct something *next;
void *data;
};
struct something *prev_ptr = ...;
struct something *new_ptr = kmalloc(sizeof(*new_ptr), GFP_KERNEL);
new_ptr-next = NULL;
new_ptr-data = some_value;
mb();
prev_ptr-next = new_ptr;
You're introducing a custom API, which is open-coded repeatedly throughout
your module.
All linked lists (at least, new ones) must use the standard kernel list
API.
Performance is not critical because this mb() is called
only when appending new entry to the singly-linked list.
Most of these uses appear to be slow path or nested inside other locks,
while overall, performance is likely to be dominated by your string
matching and permission checking. Use of mb(), which is typically
considered less understandable, in this case does not appear to be
justified vs. normal locking, and you also need to use the standard list
API. If performance really is an issue, then consider RCU.
- James
--
James Morris
[EMAIL PROTECTED]
-
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/
Re: [TOMOYO 05/15](repost) Domain transition handler functions.
James Morris [EMAIL PROTECTED] writes: All linked lists (at least, new ones) must use the standard kernel list API. Really? Why? That rule is new to me. Would also seem very limiting especially since the standard kernel lists do not allow to express important patterns (like single linked lists) I don't think that is a requirement. -Andi - 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/
