arch/x86_64/mm/extable.c

   1 /*
   2  * linux/arch/x86_64/mm/extable.c
   3  */
   4
   5 #include <linux/config.h>
   6 #include <linux/module.h>
   7 #include <linux/spinlock.h>
   8 #include <linux/init.h>
   9 #include <asm/uaccess.h>
  10
  11 /* Simple binary search */
  12 const struct exception_table_entry *
  13 search_extable(const struct exception_table_entry *first,
  14                const struct exception_table_entry *last,
  15                unsigned long value)
  16 {
  17         /* Work around a B stepping K8 bug */
  18         if ((value >> 32) == 0)
  19                 value |= 0xffffffffUL << 32;
  20
  21         while (first <= last) {
  22                 const struct exception_table_entry *mid;
  23                 long diff;
  24
  25                 mid = (last - first) / 2 + first;
  26                 diff = mid->insn - value;
  27                 if (diff == 0)
  28                         return mid;
  29                 else if (diff < 0)
  30                         first = mid+1;
  31                 else
  32                         last = mid-1;
  33         }
  34         return NULL;
  35 }
  36
  37 /* When an exception handler is in an non standard section (like __init)
  38    the fixup table can end up unordered. Fix that here. */
  39 void sort_extable(struct exception_table_entry *start,
  40                   struct exception_table_entry *finish)
  41 {
  42         struct exception_table_entry *e;
  43         int change;
  44
  45         /* The input is near completely presorted, which makes bubble sort the
  46            best (and simplest) sort algorithm. */
  47         do {
  48                 change = 0;
  49                 for (e = start+1; e < finish; e++) {
  50                         if (e->insn < e[-1].insn) {
  51                                 struct exception_table_entry tmp = e[-1];
  52                                 e[-1] = e[0];
  53                                 e[0] = tmp;
  54                                 change = 1;
  55                         }
  56                 }
  57         } while (change != 0);
  58 }