Re: [RFC PATCH v1.9 12/14] livepatch: create per-task consistency model

From: Josh Poimboeuf
Date: Thu Apr 14 2016 - 12:40:01 EST


On Thu, Apr 14, 2016 at 11:25:18AM +0200, Miroslav Benes wrote:
> On Fri, 25 Mar 2016, Josh Poimboeuf wrote:
>
> > Add a basic per-task consistency model. This is the foundation which
> > will eventually enable us to patch those ~10% of security patches which
> > change function prototypes and/or data semantics.
> >
> > When a patch is enabled, livepatch enters into a transition state where
> > tasks are converging from the old universe to the new universe. If a
> > given task isn't using any of the patched functions, it's switched to
> > the new universe. Once all the tasks have been converged to the new
> > universe, patching is complete.
> >
> > The same sequence occurs when a patch is disabled, except the tasks
> > converge from the new universe to the old universe.
> >
> > The /sys/kernel/livepatch/<patch>/transition file shows whether a patch
> > is in transition. Only a single patch (the topmost patch on the stack)
> > can be in transition at a given time. A patch can remain in the
> > transition state indefinitely, if any of the tasks are stuck in the
> > previous universe.
> >
> > A transition can be reversed and effectively canceled by writing the
> > opposite value to the /sys/kernel/livepatch/<patch>/enabled file while
> > the transition is in progress. Then all the tasks will attempt to
> > converge back to the original universe.
>
> So after spending some time with this patch I must say hats off to you. I
> haven't managed to find anything serious yet and I doubt I would. Few
> things below.

Great!

> > +/*
> > + * klp_update_task_universe() - change the patched state of a task
> > + * @task: The task to change
> > + *
> > + * Converts the patched state of the task so that it will switch to the set of
> > + * functions in the goal universe.
> > + */
> > +static inline void klp_update_task_universe(struct task_struct *task)
> > +{
> > + /*
> > + * The corresponding write barriers are in klp_init_transition() and
> > + * klp_start_transition(). See the comments there for an explanation.
> > + */
> > + smp_rmb();
> > +
> > + task->klp_universe = klp_universe_goal;
> > +}
>
> I wonder whether we should introduce a static_key for this function.
> klp_update_task_universe() is called in some important code paths and it
> is called everytime if CONFIG_LIVEPATCH is on. It does not matter much for
> syscall paths, because we enter slowpath there only if TIF_KLP_NEED_UPDATE
> is set and that is set iff patching is in progress. But we call the
> function also elsewhere. So maybe it would be nice to introduce static_key
> in the function which would be on if the patching is in progress and off
> if not.
>
> Maybe it is just an overoptimization though.

klp_update_task_universe() is called from:

- exit_to_usermode_loop() (slow path for syscall/irq exit)
- copy_process() (though I'll be changing this code so children inherit
parents' flags)
- init_idle()
- cpu_idle_loop()
- various places in livepatch code

I think none of those are fast paths, so my feeling is that a static key
would be overkill.

> [...]
>
> > +static bool klp_try_switch_task(struct task_struct *task)
> > +{
> > + struct rq *rq;
> > + unsigned long flags;
> > + int ret;
> > + bool success = false;
> > +
> > + /* check if this task has already switched over */
> > + if (task->klp_universe == klp_universe_goal)
> > + return true;
>
> [...]
>
> > +/*
> > + * This function can be called in the middle of an existing transition to
> > + * reverse the direction of the universe goal. This can be done to effectively
> > + * cancel an existing enable or disable operation if there are any tasks which
> > + * are stuck in the starting universe.
> > + */
> > +void klp_reverse_transition(void)
> > +{
> > + struct klp_patch *patch = klp_transition_patch;
> > +
> > + klp_start_transition(!klp_universe_goal);
> > + klp_try_complete_transition();
> > +
> > + patch->enabled = !patch->enabled;
> > +}
>
> This function could be called iff the patching is in progress, there are
> some not-yet-migrated tasks and we wait for scheduled workqueue to run
> klp_try_complete_transition() again, right? I have two questions.
>
> 1. Is the call to klp_try_complete_transition() here necessary? It would
> be called via workqueue, wouldn't it? I suspect we don't gain much with
> this and we introduce possible future problems because of "double
> success" of klp_try_complete_transition() (nothing serious there as of
> now though). But I might be wrong because I got really confused by this
> piece of code and its context :)

Yeah, the call to klp_try_complete_transition() isn't necessary because
of the workqueue. It's still kind of nice to have though, because it
tries to transition immediately rather than waiting for the work (and we
might end up deciding to change the delayed work frequency to be less
often than once per second).

I can't really envision that future bugs related to "double success"
would be much to worry about. The work function does check for
klp_transition_patch beforehand, and if it didn't,
klp_complete_transition() would die loudly with a NULL pointer
dereference. Of course, it's always hard to anticipate future code
changes and I could be completely wrong.

So I would vote to keep this call, but I don't feel too strongly about
it since it isn't strictly needed.

> 2. klp_reverse_transition() works well because not-yet-migrated tasks are
> still in KLP_UNIVERSE_OLD (without loss of generality) and since
> klp_universe_goal is swapped they are in fact in their target universe.
> klp_try_switch_task() returns immediately in such case. The rest is
> migrated in an ordinary way.
>
> What about TIF_KLP_NEED_UPDATE (I know it is introduced in later patch but
> it is easier to discuss it here)? klp_start_transition() resets the flag
> for all the task. Shouldn't the flag be cleared for the task in
> klp_try_switch_task() if task->klp_universe == klp_universe_goal? In fact
> it does not matter if it is set. The patching success is determined by
> klp_func->klp_universe booleans. But those tasks would needlessly go
> through syscall slowpaths (see note above about static_key) which could
> hurt performance.
>
> Does this make sense?

I agree with you, but for a different reason :-)

And actually there's another way this could happen: if a task is forked
during klp_start_transition() after setting the universe goal but before
setting the thread flags, it would already be transitioned but its flag
would get unnecessarily set. (Though as I mentioned above, the
copy_process() code will be changed anyway, so that should no longer be
an issue).

But I don't think it's really a performance issue, because:

1) Assuming a reliable stack, in most cases the majority of tasks are
transitioned immediately. So when reversing the transition, there
would be only a few tasks that would get the flag set unnecessarily.

2) For those tasks which do have the flag set unnecessarily, only the
next syscall will do the slow path. After that the flag gets
cleared. So it only slows down a single syscall for each task. At a
macro level, that's just a drop in the bucket for performance and,
IMO, not worth worrying about and adding (potentially buggy) code
for.

However, I can think of another reason setting the flag unnecessarily
might be bad: it's just conceptually confusing and could maybe lead to
bugs. (ok, here we go trying to predict the future again!)

Specifically, after klp_complete_transition(), a reasonable livepatch
developer (is that an oxymoron? ;-)) might assume that all tasks'
TIF_KLP_NEED_UPDATE flags are cleared and might write code which makes
that assumption.

And, even with today's code it's kind of hard to convince myself that
having a spurious TIF_KLP_NEED_UPDATE flag set from a previous patching
operation won't cause issues on the next patch.

So maybe we should do as you suggest and clear the flag in
klp_try_switch_task() if the task is already in the goal universe.

Or if we wanted to be paranoid we could just clear all the flags in
klp_complete_transition(), but maybe that's a little too sloppy/lazy?

> [...]
>
> transition.h:
> >
> > +extern void klp_init_transition(struct klp_patch *patch, int universe);
> > +extern void klp_start_transition(int universe);
> > +extern void klp_reverse_transition(void);
> > +extern bool klp_try_complete_transition(void);
> > +extern void klp_complete_transition(void);
>
> externs are superfluous here and we do not have them in other header
> files.

Ah, right.

> Anyway, great job!

Thanks! And thanks for the thoughtful reviews!

--
Josh