| Message ID | 1418226513-14105-2-git-send-email-a.hajda@samsung.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Wed, Dec 10, 2014 at 04:48:19PM +0100, Andrzej Hajda wrote: > track is a generic framework for safe tracking presence of any kernel objects > having an id. There are no special requirements about type of object or its > id. Id shall be unique. This is pretty confusing, when it talks about "kernel objects" that sounds like it means struct kobject but in fact there's no connection with that or any of the other kernel object stuff. Perhaps it makes sense but it should be addressed. > Typical usage of the framework by consumer looks as follow: > 1. Consumer registers notifier callback for objects with given id. This is also a custom thing not connected with the notifier mechanism implemented by struct notifier_block. Again this should probably be addressed, even if it's just used internally it seems like there should be some opportunity for code reuse here. > + case track_task_up: > + node = track_get_node(track, task->type, task->id, true); > + > + node->up = true; > + node->data = task->data; > + list_for_each_entry_safe(itb, node->itb_next, &node->itb_head, > + list) > + itb->callback(itb, node->data, true); > + return; > + case track_task_down: I'm not sure the up and down naming is the most obvious naming for users. It's obviously inspired by semaphores but it's not entirely obvious that this is going to make things clear and meaningful for someone trying to understand the interface. > +static int track_process_queue(struct tracker *track) > +{ > + struct track_task *task, *ptask = NULL; > + unsigned long flags; > + bool empty; > + > + /* Queue non-emptiness is used as a sentinel to prevent processing > + * by multiple threads, so we cannot delete entry from the queue > + * until it is processed. > + */ > + while (true) { > + spin_lock_irqsave(&track->queue_lock, flags); > + > + if (ptask) > + list_del(&ptask->list); > + task = list_first_entry(&track->queue, > + struct track_task, list); > + > + empty = list_empty(&track->queue); > + if (empty) > + complete_all(&track->queue_empty); > + > + spin_unlock_irqrestore(&track->queue_lock, flags); Here we get a task from the head of the list and drop the lock, leaving the task on the list... > + kfree(ptask); > + > + if (empty) > + break; > + > + track_process_task(track, task); ...we then go and do some other stuff, including processing that task, without the lock or or any other means I can see of excluding other users before going round and removing the task. This seems to leave us vulnerable to double execution. I *think* this is supposed to be handled by your comment "Provider should take care of calling notifications synchronously in proper order" in the changelog but that's a bit obscure, it's not specific about what the requirements are (or what the limits are supposed to be on the notification callbacks). I'm also unclear what is supposed to happen if adding a notification races with removing the thing being watched.
Hi Mark, Thanks for review. Mark Brown wrote on 12.12.2014 17:36: > On Wed, Dec 10, 2014 at 04:48:19PM +0100, Andrzej Hajda wrote: >> track is a generic framework for safe tracking presence of any kernel objects >> having an id. There are no special requirements about type of object or its >> id. Id shall be unique. > > This is pretty confusing, when it talks about "kernel objects" that > sounds like it means struct kobject but in fact there's no connection > with that or any of the other kernel object stuff. Perhaps it makes > sense but it should be addressed. > OK >> Typical usage of the framework by consumer looks as follow: >> 1. Consumer registers notifier callback for objects with given id. > > This is also a custom thing not connected with the notifier mechanism > implemented by struct notifier_block. Again this should probably be > addressed, even if it's just used internally it seems like there should > be some opportunity for code reuse here. I though about using notfier_block, but beside the struct itself there wouldn't be too much code to reuse. In my previous attempt of this framework more arguments were passed to the callback so I have dropped this idea completely, but now after simplifying the callback it fits better. > >> + case track_task_up: >> + node = track_get_node(track, task->type, task->id, true); >> + >> + node->up = true; >> + node->data = task->data; >> + list_for_each_entry_safe(itb, node->itb_next, &node->itb_head, >> + list) >> + itb->callback(itb, node->data, true); >> + return; >> + case track_task_down: > > I'm not sure the up and down naming is the most obvious naming for > users. It's obviously inspired by semaphores but it's not entirely > obvious that this is going to make things clear and meaningful for > someone trying to understand the interface. In my 1st attempt I have called the framework interface_tracker, so it was named ifup/ifdown after unix commands:) Now it is less obvious. Finding good names is always painful, anyway I will think about it. > >> +static int track_process_queue(struct tracker *track) >> +{ >> + struct track_task *task, *ptask = NULL; >> + unsigned long flags; >> + bool empty; >> + >> + /* Queue non-emptiness is used as a sentinel to prevent processing >> + * by multiple threads, so we cannot delete entry from the queue >> + * until it is processed. >> + */ >> + while (true) { >> + spin_lock_irqsave(&track->queue_lock, flags); >> + >> + if (ptask) >> + list_del(&ptask->list); >> + task = list_first_entry(&track->queue, >> + struct track_task, list); >> + >> + empty = list_empty(&track->queue); >> + if (empty) >> + complete_all(&track->queue_empty); >> + >> + spin_unlock_irqrestore(&track->queue_lock, flags); > > Here we get a task from the head of the list and drop the lock, leaving > the task on the list... Yes and it is explained in the comment few lines above. > >> + kfree(ptask); >> + >> + if (empty) >> + break; >> + >> + track_process_task(track, task); > > ...we then go and do some other stuff, including processing that task, > without the lock or or any other means I can see of excluding other > users before going round and removing the task. This seems to leave us > vulnerable to double execution. No, if you look at track_add_task function you will see that the queue is processed only if it is initially empty, otherwise the task is only added to the queue, so it will be processed after processing earlier tasks. So the rule is that if someone add task to the queue it checks if the queue is empty, in such case it process all tasks from the queue until the queue becomes empty, even the tasks added by other processed. This way all tasks are serialized. > I *think* this is supposed to be > handled by your comment "Provider should take care of calling > notifications synchronously in proper order" in the changelog but that's > a bit obscure, it's not specific about what the requirements are (or > what the limits are supposed to be on the notification callbacks). No, this comment is just to avoid advertising object (ie calling track_up) that can be just removed by concurrent thread. > > I'm also unclear what is supposed to happen if adding a notification > races with removing the thing being watched. > The sequence should be always as follows: 1. create thing, then call track_up(thing). ... 2. call track_down(thing) then remove thing. If we put 1 into probe and 2 into remove callback of the driver it will be safe - we are synchronised by device_lock. But if, for some reason, we want to create object after probe we should do own synchronization or just put device_lock around 1. The same applies if we want to remove object earlier. This is the comment above about. I will expand it to more verbose explanation. Regards Andrzej
On Sat, Dec 13, 2014 at 12:12:19AM +0100, AH wrote: > Mark Brown wrote on 12.12.2014 17:36: > >On Wed, Dec 10, 2014 at 04:48:19PM +0100, Andrzej Hajda wrote: > >>+ kfree(ptask); > >>+ > >>+ if (empty) > >>+ break; > >>+ > >>+ track_process_task(track, task); > >...we then go and do some other stuff, including processing that task, > >without the lock or or any other means I can see of excluding other > >users before going round and removing the task. This seems to leave us > >vulnerable to double execution. > No, if you look at track_add_task function you will see that the queue is > processed only if it is initially empty, otherwise the task is only added to > the queue, so it will be processed after processing earlier tasks. > So the rule is that if someone add task to the queue it checks if the queue > is empty, in such case it process all tasks from the queue until > the queue becomes empty, even the tasks added by other processed. > This way all tasks are serialized. This is all pretty fiddly and seems fragile - if nothing else the code seems undercommented since the above is only going to be apparent with following through multiple functions and we're relying on both owner and list emptiness with more than one place where a task can get processed. > >I'm also unclear what is supposed to happen if adding a notification > >races with removing the thing being watched. > The sequence should be always as follows: > 1. create thing, then call track_up(thing). > ... > 2. call track_down(thing) then remove thing. > If we put 1 into probe and 2 into remove callback of the driver it will be > safe - we are synchronised by device_lock. But if, for some reason, we want > to create object after probe we should do own synchronization or just put > device_lock around 1. The same applies if we want to remove > object earlier. This is the comment above about. I will expand it to more > verbose explanation. You can't rely on the device lock here since this isn't tied to kobjects or anything at all - it's a freestanding interface someone could pick up and use in another context. Besides, that isn't really my concern - my concern is what happens if something asks to wait for
On 12/15/2014 01:55 PM, Mark Brown wrote: > On Sat, Dec 13, 2014 at 12:12:19AM +0100, AH wrote: >> Mark Brown wrote on 12.12.2014 17:36: >>> On Wed, Dec 10, 2014 at 04:48:19PM +0100, Andrzej Hajda wrote: >>>> + kfree(ptask); >>>> + >>>> + if (empty) >>>> + break; >>>> + >>>> + track_process_task(track, task); >>> ...we then go and do some other stuff, including processing that task, >>> without the lock or or any other means I can see of excluding other >>> users before going round and removing the task. This seems to leave us >>> vulnerable to double execution. >> No, if you look at track_add_task function you will see that the queue is >> processed only if it is initially empty, otherwise the task is only added to >> the queue, so it will be processed after processing earlier tasks. >> So the rule is that if someone add task to the queue it checks if the queue >> is empty, in such case it process all tasks from the queue until >> the queue becomes empty, even the tasks added by other processed. >> This way all tasks are serialized. > This is all pretty fiddly and seems fragile - if nothing else the code > seems undercommented since the above is only going to be apparent with > following through multiple functions and we're relying on both owner and > list emptiness with more than one place where a task can get processed. I have changed it already to test queue owner, this way it should be more clear. > >>> I'm also unclear what is supposed to happen if adding a notification >>> races with removing the thing being watched. >> The sequence should be always as follows: >> 1. create thing, then call track_up(thing). >> ... >> 2. call track_down(thing) then remove thing. >> If we put 1 into probe and 2 into remove callback of the driver it will be >> safe - we are synchronised by device_lock. But if, for some reason, we want >> to create object after probe we should do own synchronization or just put >> device_lock around 1. The same applies if we want to remove >> object earlier. This is the comment above about. I will expand it to more >> verbose explanation. > You can't rely on the device lock here since this isn't tied to kobjects > or anything at all - it's a freestanding interface someone could pick up > and use in another context. Besides, that isn't really my concern - my > concern is what happens if something asks to wait for But I do not rely here on device_lock, I just point out that 1 and 2 should be synchronized and as a common way is to put such things into probe and remove, device_lock can do the synchronization for us in such case, so no need for additional synchronization. And to make everything clear, track_up will not be called by the driver directly, it shall be called by respective resource framework functions, for example by regulator_register and regulator_unregister. And regarding your initial/real concern, I guess you mean this one: >> I'm also unclear what is supposed to happen if adding a notification >> races with removing the thing being watched. I guess you mean registering notifier and removal of thing it is supposed to watch. As all track tasks are serialized these two will be serialized also so we can have only two scenarios: 1. a) register notifier - thing is up, so notifier will be immediately called with info that the thing is up b) remove thing - thing will be down, so notifier will be called with info that the thing will be removed 2. a) remove thing - notifier is not yet registered, so callback will not be called, b) register notifier - thing is already removed, so callback will not be called. I hope this is what you were asking for. Regards Andrzej
diff --git a/drivers/base/Makefile b/drivers/base/Makefile index 6922cd6..4edff7d 100644 --- a/drivers/base/Makefile +++ b/drivers/base/Makefile @@ -4,7 +4,7 @@ obj-y := component.o core.o bus.o dd.o syscore.o \ driver.o class.o platform.o \ cpu.o firmware.o init.o map.o devres.o \ attribute_container.o transport_class.o \ - topology.o container.o + topology.o container.o track.o obj-$(CONFIG_DEVTMPFS) += devtmpfs.o obj-$(CONFIG_DMA_CMA) += dma-contiguous.o obj-y += power/ diff --git a/drivers/base/track.c b/drivers/base/track.c new file mode 100644 index 0000000..8cf0492 --- /dev/null +++ b/drivers/base/track.c @@ -0,0 +1,241 @@ +/* + * Generic framework for tracking named object + * + * Copyright (c) 2014 Samsung Electronics Co., Ltd + * Andrzej Hajda <a.hajda@samsung.com> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * track is a generic framework for safe tracking presence of any kernel objects + * having an id. There are no special requirements about type of object or its + * id. Id shall be unique. + * Typical usage of the framework by consumer looks as follow: + * 1. Consumer registers notifier callback for objects with given id. + * 2. If the object is present consumer is notified immediately, otherwise it + * will be notified immediately after object creation. + * 3. If the object is about to be removed notification is sent to the consumer + * just before removal. + * 4. When consumer do not need the object anymore it unregisters its notifier + * callback. If the object is present during notifier unregistration + * notification about removal of the object is sent to the consumer. + * + * All notification callbacks are serialized so the consumer do not need use + * additional mechanisms to prevent callback races. Consumer should assume that + * object is valid only between up and down notification callbacks inclusive. + * + * Framework usage by object provider is simple: + * 1. When object becomes available it notifies framework about it. + * 2. When object becomes unavailable it notifies framework about it. + * + * Provider should take care of calling notifications synchronously in proper + * order. + * + * The framework does not uses locks during notification calls, so it is safe + * to call framework functions from the callbacks. This feature allows to model + * complex object dependencies without deadlock risk. + * + * Some framework functions can sleep so the framework should be used in process + * context. + * + */ +#include <linux/sched.h> +#include <linux/slab.h> +#include <linux/track.h> + +struct track_task { + struct list_head list; + enum track_task_id task_id; + + unsigned long type; + const void *id; + union { + void *data; + struct track_block *itb; + }; +}; + +struct track_node { + struct list_head list; + struct list_head itb_head; + struct track_block *itb_next; + const void *id; + unsigned long type; + void *data; + bool up; +}; + +static struct track_node * +track_get_node(struct tracker *track, unsigned long type, const void *id, + bool create) +{ + struct track_node *node; + + list_for_each_entry(node, &track->nodes, list) { + if (node->type == type && node->id == id) + return node; + } + + if (!create) + return NULL; + + node = kmalloc(sizeof(*node), GFP_KERNEL); + if (!node) + return NULL; + + node->id = id; + node->type = type; + node->up = false; + INIT_LIST_HEAD(&node->itb_head); + list_add(&node->list, &track->nodes); + + return node; +} + +static void track_process_task(struct tracker *track, struct track_task *task) +{ + struct track_block *itb; + struct track_node *node; + + switch (task->task_id) { + case track_task_register: + node = track_get_node(track, task->type, task->id, true); + list_add_tail(&task->itb->list, &node->itb_head); + + if (node->up) + task->itb->callback(task->itb, node->data, true); + return; + case track_task_unregister: + node = track_get_node(track, task->type, task->id, false); + if (WARN_ON(!node)) + return; + + if (node->up) + task->itb->callback(task->itb, node->data, false); + + if (node->itb_next == task->itb) + node->itb_next = list_next_entry(node->itb_next, list); + list_del(&task->itb->list); + + if (list_empty(&node->itb_head) && !node->up) { + list_del(&node->list); + kfree(node); + } + return; + case track_task_up: + node = track_get_node(track, task->type, task->id, true); + + node->up = true; + node->data = task->data; + list_for_each_entry_safe(itb, node->itb_next, &node->itb_head, + list) + itb->callback(itb, node->data, true); + return; + case track_task_down: + node = track_get_node(track, task->type, task->id, false); + + if (WARN_ON(!node)) + return; + + WARN_ON(!node->up); + + if (list_empty(&node->itb_head)) { + list_del(&node->list); + kfree(node); + return; + } + + node->up = false; + node->data = task->data; + + list_for_each_entry_safe(itb, node->itb_next, &node->itb_head, + list) + itb->callback(itb, node->data, false); + } +} + +static int track_process_queue(struct tracker *track) +{ + struct track_task *task, *ptask = NULL; + unsigned long flags; + bool empty; + + /* Queue non-emptiness is used as a sentinel to prevent processing + * by multiple threads, so we cannot delete entry from the queue + * until it is processed. + */ + while (true) { + spin_lock_irqsave(&track->queue_lock, flags); + + if (ptask) + list_del(&ptask->list); + task = list_first_entry(&track->queue, + struct track_task, list); + + empty = list_empty(&track->queue); + if (empty) + complete_all(&track->queue_empty); + + spin_unlock_irqrestore(&track->queue_lock, flags); + + kfree(ptask); + + if (empty) + break; + + track_process_task(track, task); + ptask = task; + } + + return 0; +} + +int track_add_task(struct tracker *track, enum track_task_id task_id, + unsigned long type, const void *id, void *data, bool sync) +{ + struct track_task *task; + unsigned long flags; + bool empty, owner; + + task = kmalloc(sizeof(*task), GFP_KERNEL); + if (!task) + return -ENOMEM; + + task->task_id = task_id; + task->id = id; + task->type = type; + task->data = data; + + spin_lock_irqsave(&track->queue_lock, flags); + + empty = list_empty(&track->queue); + if (empty) { + reinit_completion(&track->queue_empty); + track->queue_owner = current; + } else { + owner = (track->queue_owner == current); + } + + if (empty || !owner) + list_add(&task->list, &track->queue); + + spin_unlock_irqrestore(&track->queue_lock, flags); + + pr_debug("%s:%d: task=%c type=%ld id=%p\n", __func__, __LINE__, + "ru+-"[task_id], type, id); + + if (empty) + return track_process_queue(track); + + if (owner) { + track_process_task(track, task); + kfree(task); + return 0; + } + + if (sync) + wait_for_completion(&track->queue_empty); + + return 0; +} diff --git a/include/linux/track.h b/include/linux/track.h new file mode 100644 index 0000000..b1eed60 --- /dev/null +++ b/include/linux/track.h @@ -0,0 +1,148 @@ +#ifndef TRACK_H +#define TRACK_H + +#include <linux/completion.h> +#include <linux/list.h> +#include <linux/spinlock.h> +#include <linux/types.h> + +struct list_head; +struct track_block; +struct tracker; + +typedef void (*track_fn_t)(struct track_block *itb, void *data, bool on); + +/** + * struct track_block - structure used by track consumers to register callback + * @callback: Pointer to notification function provided by consumer + * @list: field used by track core to chain blocks + * + * struct track_block is passed to the framework during callback registration, + * it should be valid until callback unregistration. + * Usually it can be embedded in drivers private data, so callback function can + * get pointer to private data using container_of mechanism. + * + */ +struct track_block { + track_fn_t callback; + struct list_head list; +}; + +enum track_task_id { + track_task_register, + track_task_unregister, + track_task_up, + track_task_down, +}; + +/** + * struct tracker - the main structure for tracking objects + * @queue: queue of tasks to do + * @queue_lock: lock protecting @queue access + * @queue_empty: completion fired when queue becomes empty + * @queue_owner: id of task processing queue + * @nodes: list head of track_nodes + * + * struct tracker - is the main structure used to track and synchronize + * framework functions and callbacks. There can be many independent trackers in + * the system. + */ +struct tracker { + struct list_head queue; + spinlock_t queue_lock; + struct completion queue_empty; + struct task_struct *queue_owner; + struct list_head nodes; +}; + +/** + * DEFINE_TRACKER - define the main structure for object tracking + * @x: name of the structure + * + * This macro defines and initializes tracker structure. + */ +#define DEFINE_TRACKER(x) \ + struct tracker x = { \ + .queue = LIST_HEAD_INIT(x.queue), \ + .queue_lock = __SPIN_LOCK_UNLOCKED(x.queue_lock), \ + .queue_empty = COMPLETION_INITIALIZER(x.queue_empty), \ + .nodes = LIST_HEAD_INIT(x.nodes), \ + } + +/* internal function, exposed only to allow inline public functions */ +extern int track_add_task(struct tracker *track, enum track_task_id task_id, + unsigned long type, const void *id, void *data, bool sync); + +/** + * track_register - register track callback + * @track: pointer to tracker main structure + * @itb: block containing registered callback + * @type: tracked object type, defined by user + * @id: object id + * + * track_register registers callback which will receive notifications about + * presence of object identified by pair (@type, @id). If during registration + * tracked object is present, notification callback will be sent immediately. + */ +static inline int track_register(struct tracker *track, struct track_block *itb, + unsigned long type, const void *id) +{ + return track_add_task(track, track_task_register, type, id, itb, + false); +} + +/** + * track_unregister - unregister track callback + * @track: pointer to tracker main structure + * @itb: block containing registered callback + * @type: tracked object type + * @id: object id + * + * track_unregister unregisters previously registered callback. If during + * unregistration tracked object is present, notification is send immediately. + */ +static inline int track_unregister(struct tracker *track, + struct track_block *itb, unsigned long type, const void *id) +{ + return track_add_task(track, track_task_unregister, type, id, itb, + true); +} + +/** + * track_up - notifies about object appearance + * @track: pointer to tracker main structure + * @type: tracked object type + * @id: object id + * @data: optional data pointer, usually it should be object pointer + * + * track_up sends notification about object appearance to all callbacks + * registered to track this object. It should be called after the object is + * fully created. It is up to provider to synchronize calls to track_up and + * track_down for given object. + */ +static inline int track_up(struct tracker *track, unsigned long type, + const void *id, void *data) +{ + return track_add_task(track, track_task_up, type, id, data, false); +} + +/** + * track_down - notifies about object disappearance + * @track: pointer to tracker main structure + * @type: tracked object type + * @id: object id + * @data: optional data pointer, usually it should be object pointer + * + * track_up sends notification about object disappearance to all callbacks + * registered to track this object. It should be called before the object is + * destroyed. It is up to provider to synchronize calls to track_up and + * track_down for given object. + */ +static inline int track_down(struct tracker *track, unsigned long type, + const void *id, void *data) +{ + return track_add_task(track, track_task_down, type, id, data, + true); +} + +#endif /* TRACK_H */
track is a generic framework for safe tracking presence of any kernel objects having an id. There are no special requirements about type of object or its id. Id shall be unique. Typical usage of the framework by consumer looks as follow: 1. Consumer registers notifier callback for objects with given id. 2. If the object is present consumer is notified immediately, otherwise it will be notified immediately after object creation. 3. If the object is about to be removed notification is sent to the consumer just before removal. 4. When consumer do not need the object anymore it unregisters its notifier callback. If the object is present during notifier unregistration notification about removal of the object is sent to the consumer. All notification callbacks are serialized so the consumer do not need use additional mechanisms to prevent callback races. Consumer should assume that object is valid only between up and down notification callbacks inclusive. Framework usage by object provider is simple: 1. When object becomes available it notifies framework about it. 2. When object becomes unavailable it notifies framework about it. Provider should take care of calling notifications synchronously in proper order. The framework does not uses locks during notification calls, so it is safe to call framework functions from the callbacks. This feature allows to model complex object dependencies without deadlock risk. Some framework functions can sleep so the framework should be used in process context. Signed-off-by: Andrzej Hajda <a.hajda@samsung.com> --- drivers/base/Makefile | 2 +- drivers/base/track.c | 241 ++++++++++++++++++++++++++++++++++++++++++++++++++ include/linux/track.h | 148 +++++++++++++++++++++++++++++++ 3 files changed, 390 insertions(+), 1 deletion(-) create mode 100644 drivers/base/track.c create mode 100644 include/linux/track.h