mm/oom_kill.c

   1 /*
   2  *  linux/mm/oom_kill.c
   3  *
   4  *  Copyright (C)  1998,2000  Rik van Riel
   5  *      Thanks go out to Claus Fischer for some serious inspiration and
   6  *      for goading me into coding this file...
   7  *
   8  *  The routines in this file are used to kill a process when
   9  *  we're seriously out of memory. This gets called from __alloc_pages()
  10  *  in mm/page_alloc.c when we really run out of memory.
  11  *
  12  *  Since we won't call these routines often (on a well-configured
  13  *  machine) this file will double as a 'coding guide' and a signpost
  14  *  for newbie kernel hackers. It features several pointers to major
  15  *  kernel subsystems and hints as to where to find out what things do.
  16  */
  17
  18 #include <linux/mm.h>
  19 #include <linux/sched.h>
  20 #include <linux/swap.h>
  21 #include <linux/timex.h>
  22 #include <linux/jiffies.h>
  23 #include <linux/cpuset.h>
  24
  25 int sysctl_panic_on_oom;
  26 /* #define DEBUG */
  27
  28 /**
  29  * badness - calculate a numeric value for how bad this task has been
  30  * @p: task struct of which task we should calculate
  31  * @uptime: current uptime in seconds
  32  *
  33  * The formula used is relatively simple and documented inline in the
  34  * function. The main rationale is that we want to select a good task
  35  * to kill when we run out of memory.
  36  *
  37  * Good in this context means that:
  38  * 1) we lose the minimum amount of work done
  39  * 2) we recover a large amount of memory
  40  * 3) we don't kill anything innocent of eating tons of memory
  41  * 4) we want to kill the minimum amount of processes (one)
  42  * 5) we try to kill the process the user expects us to kill, this
  43  *    algorithm has been meticulously tuned to meet the principle
  44  *    of least surprise ... (be careful when you change it)
  45  */
  46
  47 unsigned long badness(struct task_struct *p, unsigned long uptime)
  48 {
  49         unsigned long points, cpu_time, run_time, s;
  50         struct mm_struct *mm;
  51         struct task_struct *child;
  52
  53         task_lock(p);
  54         mm = p->mm;
  55         if (!mm) {
  56                 task_unlock(p);
  57                 return 0;
  58         }
  59
  60         /*
  61          * The memory size of the process is the basis for the badness.
  62          */
  63         points = mm->total_vm;
  64
  65         /*
  66          * After this unlock we can no longer dereference local variable `mm'
  67          */
  68         task_unlock(p);
  69
  70         /*
  71          * Processes which fork a lot of child processes are likely
  72          * a good choice. We add half the vmsize of the children if they
  73          * have an own mm. This prevents forking servers to flood the
  74          * machine with an endless amount of children. In case a single
  75          * child is eating the vast majority of memory, adding only half
  76          * to the parents will make the child our kill candidate of choice.
  77          */
  78         list_for_each_entry(child, &p->children, sibling) {
  79                 task_lock(child);
  80                 if (child->mm != mm && child->mm)
  81                         points += child->mm->total_vm/2 + 1;
  82                 task_unlock(child);
  83         }
  84
  85         /*
  86          * CPU time is in tens of seconds and run time is in thousands
  87          * of seconds. There is no particular reason for this other than
  88          * that it turned out to work very well in practice.
  89          */
  90         cpu_time = (cputime_to_jiffies(p->utime) + cputime_to_jiffies(p->stime))
  91                 >> (SHIFT_HZ + 3);
  92
  93         if (uptime >= p->start_time.tv_sec)
  94                 run_time = (uptime - p->start_time.tv_sec) >> 10;
  95         else
  96                 run_time = 0;
  97
  98         s = int_sqrt(cpu_time);
  99         if (s)
 100                 points /= s;
 101         s = int_sqrt(int_sqrt(run_time));
 102         if (s)
 103                 points /= s;
 104
 105         /*
 106          * Niced processes are most likely less important, so double
 107          * their badness points.
 108          */
 109         if (task_nice(p) > 0)
 110                 points *= 2;
 111
 112         /*
 113          * Superuser processes are usually more important, so we make it
 114          * less likely that we kill those.
 115          */
 116         if (cap_t(p->cap_effective) & CAP_TO_MASK(CAP_SYS_ADMIN) ||
 117                                 p->uid == 0 || p->euid == 0)
 118                 points /= 4;
 119
 120         /*
 121          * We don't want to kill a process with direct hardware access.
 122          * Not only could that mess up the hardware, but usually users
 123          * tend to only have this flag set on applications they think
 124          * of as important.
 125          */
 126         if (cap_t(p->cap_effective) & CAP_TO_MASK(CAP_SYS_RAWIO))
 127                 points /= 4;
 128
 129         /*
 130          * Adjust the score by oomkilladj.
 131          */
 132         if (p->oomkilladj) {
 133                 if (p->oomkilladj > 0)
 134                         points <<= p->oomkilladj;
 135                 else
 136                         points >>= -(p->oomkilladj);
 137         }
 138
 139 #ifdef DEBUG
 140         printk(KERN_DEBUG "OOMkill: task %d (%s) got %d points\n",
 141         p->pid, p->comm, points);
 142 #endif
 143         return points;
 144 }
 145
 146 /*
 147  * Types of limitations to the nodes from which allocations may occur
 148  */
 149 #define CONSTRAINT_NONE 1
 150 #define CONSTRAINT_MEMORY_POLICY 2
 151 #define CONSTRAINT_CPUSET 3
 152
 153 /*
 154  * Determine the type of allocation constraint.
 155  */
 156 static inline int constrained_alloc(struct zonelist *zonelist, gfp_t gfp_mask)
 157 {
 158 #ifdef CONFIG_NUMA
 159         struct zone **z;
 160         nodemask_t nodes = node_online_map;
 161
 162         for (z = zonelist->zones; *z; z++)
 163                 if (cpuset_zone_allowed(*z, gfp_mask))
 164                         node_clear((*z)->zone_pgdat->node_id,
 165                                         nodes);
 166                 else
 167                         return CONSTRAINT_CPUSET;
 168
 169         if (!nodes_empty(nodes))
 170                 return CONSTRAINT_MEMORY_POLICY;
 171 #endif
 172
 173         return CONSTRAINT_NONE;
 174 }
 175
 176 /*
 177  * Simple selection loop. We chose the process with the highest
 178  * number of 'points'. We expect the caller will lock the tasklist.
 179  *
 180  * (not docbooked, we don't want this one cluttering up the manual)
 181  */
 182 static struct task_struct *select_bad_process(unsigned long *ppoints)
 183 {
 184         struct task_struct *g, *p;
 185         struct task_struct *chosen = NULL;
 186         struct timespec uptime;
 187         *ppoints = 0;
 188
 189         do_posix_clock_monotonic_gettime(&uptime);
 190         do_each_thread(g, p) {
 191                 unsigned long points;
 192                 int releasing;
 193
 194                 /* skip the init task with pid == 1 */
 195                 if (p->pid == 1)
 196                         continue;
 197                 if (p->oomkilladj == OOM_DISABLE)
 198                         continue;
 199                 /* If p's nodes don't overlap ours, it won't help to kill p. */
 200                 if (!cpuset_excl_nodes_overlap(p))
 201                         continue;
 202
 203                 /*
 204                  * This is in the process of releasing memory so wait for it
 205                  * to finish before killing some other task by mistake.
 206                  */
 207                 releasing = test_tsk_thread_flag(p, TIF_MEMDIE) ||
 208                                                 p->flags & PF_EXITING;
 209                 if (releasing && !(p->flags & PF_DEAD))
 210                         return ERR_PTR(-1UL);
 211                 if (p->flags & PF_SWAPOFF)
 212                         return p;
 213
 214                 points = badness(p, uptime.tv_sec);
 215                 if (points > *ppoints || !chosen) {
 216                         chosen = p;
 217                         *ppoints = points;
 218                 }
 219         } while_each_thread(g, p);
 220         return chosen;
 221 }
 222
 223 /**
 224  * We must be careful though to never send SIGKILL a process with
 225  * CAP_SYS_RAW_IO set, send SIGTERM instead (but it's unlikely that
 226  * we select a process with CAP_SYS_RAW_IO set).
 227  */
 228 static void __oom_kill_task(struct task_struct *p, const char *message)
 229 {
 230         if (p->pid == 1) {
 231                 WARN_ON(1);
 232                 printk(KERN_WARNING "tried to kill init!\n");
 233                 return;
 234         }
 235
 236         task_lock(p);
 237         if (!p->mm || p->mm == &init_mm) {
 238                 WARN_ON(1);
 239                 printk(KERN_WARNING "tried to kill an mm-less task!\n");
 240                 task_unlock(p);
 241                 return;
 242         }
 243         task_unlock(p);
 244         printk(KERN_ERR "%s: Killed process %d (%s).\n",
 245                                 message, p->pid, p->comm);
 246
 247         /*
 248          * We give our sacrificial lamb high priority and access to
 249          * all the memory it needs. That way it should be able to
 250          * exit() and clear out its resources quickly...
 251          */
 252         p->time_slice = HZ;
 253         set_tsk_thread_flag(p, TIF_MEMDIE);
 254
 255         force_sig(SIGKILL, p);
 256 }
 257
 258 static int oom_kill_task(struct task_struct *p, const char *message)
 259 {
 260         struct mm_struct *mm;
 261         struct task_struct *g, *q;
 262
 263         mm = p->mm;
 264
 265         /* WARNING: mm may not be dereferenced since we did not obtain its
 266          * value from get_task_mm(p).  This is OK since all we need to do is
 267          * compare mm to q->mm below.
 268          *
 269          * Furthermore, even if mm contains a non-NULL value, p->mm may
 270          * change to NULL at any time since we do not hold task_lock(p).
 271          * However, this is of no concern to us.
 272          */
 273
 274         if (mm == NULL || mm == &init_mm)
 275                 return 1;
 276
 277         __oom_kill_task(p, message);
 278         /*
 279          * kill all processes that share the ->mm (i.e. all threads),
 280          * but are in a different thread group
 281          */
 282         do_each_thread(g, q)
 283                 if (q->mm == mm && q->tgid != p->tgid)
 284                         __oom_kill_task(q, message);
 285         while_each_thread(g, q);
 286
 287         return 0;
 288 }
 289
 290 static int oom_kill_process(struct task_struct *p, unsigned long points,
 291                 const char *message)
 292 {
 293         struct task_struct *c;
 294         struct list_head *tsk;
 295
 296         printk(KERN_ERR "Out of Memory: Kill process %d (%s) score %li and "
 297                 "children.\n", p->pid, p->comm, points);
 298         /* Try to kill a child first */
 299         list_for_each(tsk, &p->children) {
 300                 c = list_entry(tsk, struct task_struct, sibling);
 301                 if (c->mm == p->mm)
 302                         continue;
 303                 if (!oom_kill_task(c, message))
 304                         return 0;
 305         }
 306         return oom_kill_task(p, message);
 307 }
 308
 309 /**
 310  * out_of_memory - kill the "best" process when we run out of memory
 311  *
 312  * If we run out of memory, we have the choice between either
 313  * killing a random task (bad), letting the system crash (worse)
 314  * OR try to be smart about which process to kill. Note that we
 315  * don't have to be perfect here, we just have to be good.
 316  */
 317 void out_of_memory(struct zonelist *zonelist, gfp_t gfp_mask, int order)
 318 {
 319         struct task_struct *p;
 320         unsigned long points = 0;
 321
 322         if (printk_ratelimit()) {
 323                 printk("oom-killer: gfp_mask=0x%x, order=%d\n",
 324                         gfp_mask, order);
 325                 dump_stack();
 326                 show_mem();
 327         }
 328
 329         cpuset_lock();
 330         read_lock(&tasklist_lock);
 331
 332         /*
 333          * Check if there were limitations on the allocation (only relevant for
 334          * NUMA) that may require different handling.
 335          */
 336         switch (constrained_alloc(zonelist, gfp_mask)) {
 337         case CONSTRAINT_MEMORY_POLICY:
 338                 oom_kill_process(current, points,
 339                                 "No available memory (MPOL_BIND)");
 340                 break;
 341
 342         case CONSTRAINT_CPUSET:
 343                 oom_kill_process(current, points,
 344                                 "No available memory in cpuset");
 345                 break;
 346
 347         case CONSTRAINT_NONE:
 348                 if (sysctl_panic_on_oom)
 349                         panic("out of memory. panic_on_oom is selected\n");
 350 retry:
 351                 /*
 352                  * Rambo mode: Shoot down a process and hope it solves whatever
 353                  * issues we may have.
 354                  */
 355                 p = select_bad_process(&points);
 356
 357                 if (PTR_ERR(p) == -1UL)
 358                         goto out;
 359
 360                 /* Found nothing?!?! Either we hang forever, or we panic. */
 361                 if (!p) {
 362                         read_unlock(&tasklist_lock);
 363                         cpuset_unlock();
 364                         panic("Out of memory and no killable processes...\n");
 365                 }
 366
 367                 if (oom_kill_process(p, points, "Out of memory"))
 368                         goto retry;
 369
 370                 break;
 371         }
 372
 373 out:
 374         read_unlock(&tasklist_lock);
 375         cpuset_unlock();
 376
 377         /*
 378          * Give "p" a good chance of killing itself before we
 379          * retry to allocate memory unless "p" is current
 380          */
 381         if (!test_thread_flag(TIF_MEMDIE))
 382                 schedule_timeout_uninterruptible(1);
 383 }