[RFC PATCH v1.9 00/14] livepatch: hybrid consistency model

[Josh Poimboeuf]

These patches are still a work in progress, but Jiri asked that I share
them before I go on vacation next week.  Based on origin/master because
it has CONFIG_STACK_VALIDATION.

This has two consistency models: the immediate model (like in today's
code) and the new kpatch/kgraft hybrid model.

The default is the hybrid model: kgraft's per-task consistency and
syscall barrier switching combined with kpatch's stack trace switching.
There are also a number of fallback options which make it pretty
flexible, yet the code is still quite simple.

Patches are applied on a per-task basis, when the task is deemed safe to
switch over.  It uses a tiered approach to determine when a task is safe
and can be switched.

The first wave of attack is stack checking of sleeping tasks.  If no
affected functions are on the stack of a given task, the task is
switched.  In most cases this will patch most or all of the tasks on the
first try.  Otherwise it'll keep trying periodically.  This option is
only available if the architecture has reliable stacks
(CONFIG_RELIABLE_STACKTRACE and CONFIG_STACK_VALIDATION).

The next line of attack, if needed, is syscall/IRQ switching.  A task is
switched when it returns from a system call or a user space IRQ.  This
approach is less than ideal because it usually requires signaling tasks
to get them to switch.  It also doesn't work for kthreads.  But it's
still useful in some cases when user tasks get stuck sleeping on an
affected function.

For architectures which don't have reliable stacks, users have two
options:

a) use the hybrid fallback option of using only the syscall/IRQ
   switching (which is the default);

b) or they can use the immediate model (which is the model we already
   have today) by setting the patch->immediate flag.

There's also a func->immediate flag which allows users to specify that
certain functions in the patch can be applied without per-task
consistency.  This might be useful if you want to patch a common
function like schedule(), and the function change doesn't need
consistency but the rest of the patch does.

Still have a lot of TODOs, some of them are listed here.  If you see
something objectionable, it might be a good idea to make sure it's not
already on the TODO list :-)

TODO:
- actually test it
- don't use TIP_KLP_NEED_UPDATE in arch-independent code
- figure out new API to keep the use of task_rq_lock() in the sched code
- cleaner way to detect preemption on the stack
- allow patch modules to be removed.  still needs more discussion and
  thought.  maybe something like Miroslav's patch would be good:
  https://lkml.kernel.org/r/alpine.LNX.2.00.1512150857510.24899@xxxxxxxxxxxxx
- come up with a better name than universe?  KLP_STATE_PREV/NEXT?
  KLP_UNPATCHED/PATCHED?  there were some objections to the name in v1.
- update documentation for sysfs, proc, livepatch
- need atomic accesses or READ_ONCE/WRITE_ONCE anywhere?
- ability to force a patch to the goal universe
- try ftrace handler switching idea from v1 cover letter
- split up the patches better
- cc all the right people

v1.9 changes:
- revive from the dead and rebased
- reliable stacks!
- add support for immediate consistency model
- add a ton of comments
- fix up memory barriers
- remove "allow patch modules to be removed" patch for now, it still 
  needs more discussion and thought - it can be done with something
- "proc/pid/universe" -> "proc/pid/patch_status"
- remove WARN_ON_ONCE from !func condition in ftrace handler -- can
  happen because of RCU
- keep klp_mutex private by putting the work_fn in core.c
- convert states from int to boolean
- remove obsolete '@state' comments
- several header file and include improvements suggested by Jiri S
- change kallsyms_lookup_size_offset() errors from EINVAL -> ENOENT
- change proc file permissions S_IRUGO -> USR
- use klp_for_each_object/func helpers

v1 was here:
https://lkml.kernel.org/r/cover.1423499826.git.jpoimboe@xxxxxxxxxx

Josh Poimboeuf (14):
  x86/asm/head: cleanup initial stack variable
  x86/asm/head: use a common function for starting CPUs
  x86/asm/head: standardize the bottom of the stack for idle tasks
  x86: move _stext marker before head code
  sched: horrible way to detect whether a task has been preempted
  x86: add error handling to dump_trace()
  x86/stacktrace: add function for detecting reliable stack traces
  livepatch: separate enabled and patched states
  livepatch: remove unnecessary object loaded check
  livepatch: move patching functions into patch.c
  livepatch: store function sizes
  livepatch: create per-task consistency model
  livepatch: add /proc/<pid>/patch_status
  livepatch: update task universe when exiting kernel

 arch/Kconfig                       |   6 +
 arch/x86/Kconfig                   |   1 +
 arch/x86/entry/common.c            |   6 +-
 arch/x86/include/asm/realmode.h    |   2 +-
 arch/x86/include/asm/smp.h         |   3 -
 arch/x86/include/asm/stacktrace.h  |  36 +--
 arch/x86/include/asm/thread_info.h |   2 +
 arch/x86/kernel/acpi/sleep.c       |   2 +-
 arch/x86/kernel/dumpstack.c        |  67 ++++--
 arch/x86/kernel/dumpstack_32.c     |  22 +-
 arch/x86/kernel/dumpstack_64.c     |  53 +++--
 arch/x86/kernel/head_32.S          |   8 +-
 arch/x86/kernel/head_64.S          |  35 ++-
 arch/x86/kernel/smpboot.c          |   2 +-
 arch/x86/kernel/stacktrace.c       |  32 +++
 arch/x86/kernel/vmlinux.lds.S      |   2 +-
 fs/proc/base.c                     |  12 +
 include/linux/livepatch.h          |  49 ++++-
 include/linux/sched.h              |  14 +-
 include/linux/stacktrace.h         |  20 +-
 kernel/fork.c                      |   2 +
 kernel/livepatch/Makefile          |   2 +-
 kernel/livepatch/core.c            | 316 +++++++++------------------
 kernel/livepatch/patch.c           | 226 +++++++++++++++++++
 kernel/livepatch/patch.h           |  33 +++
 kernel/livepatch/transition.c      | 435 +++++++++++++++++++++++++++++++++++++
 kernel/livepatch/transition.h      |  20 ++
 kernel/sched/core.c                |  28 ++-
 kernel/sched/idle.c                |   4 +
 kernel/stacktrace.c                |   4 +-
 lib/Kconfig.debug                  |   6 +
 31 files changed, 1135 insertions(+), 315 deletions(-)
 create mode 100644 kernel/livepatch/patch.c
 create mode 100644 kernel/livepatch/patch.h
 create mode 100644 kernel/livepatch/transition.c
 create mode 100644 kernel/livepatch/transition.h

-- 
2.4.3