gator_cookies.c

   1 /**
   2  * Copyright (C) ARM Limited 2010. All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License version 2 as
   6  * published by the Free Software Foundation.
   7  *
   8  */
   9
  10 #define COOKIEMAP_ENTRIES       1024            /* must be power of 2 */
  11 #define MAX_COLLISIONS          2
  12
  13 static DEFINE_PER_CPU(uint32_t, cookie_next_key);
  14 static DEFINE_PER_CPU(uint32_t, cookie_prev_text);
  15 static DEFINE_PER_CPU(uint32_t, cookie_prev_value);
  16 static DEFINE_PER_CPU(uint64_t *, cookie_keys);
  17 static DEFINE_PER_CPU(uint32_t *, cookie_values);
  18
  19 static uint32_t *gator_crc32_table;
  20
  21 static uint32_t cookiemap_code(uint32_t value) {
  22         uint32_t cookiecode = (value >> 24) & 0xff;
  23         cookiecode = cookiecode * 31 + ((value >> 16) & 0xff);
  24         cookiecode = cookiecode * 31 + ((value >> 8) & 0xff);
  25         cookiecode = cookiecode * 31 + ((value >> 0) & 0xff);
  26         cookiecode &= (COOKIEMAP_ENTRIES-1);
  27         return cookiecode * MAX_COLLISIONS;
  28 }
  29
  30 static uint32_t gator_chksum_crc32(char *data)
  31 {
  32    register unsigned long crc;
  33    unsigned char *block = data;
  34    int i, length = strlen(data);
  35
  36    crc = 0xFFFFFFFF;
  37    for (i = 0; i < length; i++) {
  38       crc = ((crc >> 8) & 0x00FFFFFF) ^ gator_crc32_table[(crc ^ *block++) & 0xFF];
  39    }
  40
  41    return (crc ^ 0xFFFFFFFF);
  42 }
  43
  44 /*
  45  * Exists
  46  *  Pre:  [0][1][v][3]..[n-1]
  47  *  Post: [v][0][1][3]..[n-1]
  48  */
  49 static uint32_t cookiemap_exists(uint64_t key) {
  50         int cpu = raw_smp_processor_id();
  51         uint32_t cookiecode = cookiemap_code(key);
  52         uint64_t *keys = &(per_cpu(cookie_keys, cpu)[cookiecode]);
  53         uint32_t *values = &(per_cpu(cookie_values, cpu)[cookiecode]);
  54         int x;
  55
  56         for (x = 0; x < MAX_COLLISIONS; x++) {
  57                 if (keys[x] == key) {
  58                         uint32_t value = values[x];
  59                         for (; x > 0; x--) {
  60                                 keys[x] = keys[x-1];
  61                                 values[x] = values[x-1];
  62                         }
  63                         keys[0] = key;
  64                         values[0] = value;
  65                         return value;
  66                 }
  67         }
  68
  69         return 0;
  70 }
  71
  72 /*
  73  * Add
  74  *  Pre:  [0][1][2][3]..[n-1]
  75  *  Post: [v][0][1][2]..[n-2]
  76  */
  77 static void cookiemap_add(uint64_t key, uint32_t value) {
  78         int cpu = raw_smp_processor_id();
  79         int cookiecode = cookiemap_code(key);
  80         uint64_t *keys = &(per_cpu(cookie_keys, cpu)[cookiecode]);
  81         uint32_t *values = &(per_cpu(cookie_values, cpu)[cookiecode]);
  82         int x;
  83
  84         for (x = MAX_COLLISIONS-1; x > 0; x--) {
  85                 keys[x] = keys[x-1];
  86                 values[x] = keys[x-1];
  87         }
  88         keys[0] = key;
  89         values[0] = value;
  90 }
  91
  92 static inline uint32_t get_cookie(int cpu, int tgid, struct vm_area_struct *vma)
  93 {
  94         struct path *path;
  95         uint64_t key;
  96         int cookie;
  97         char *text;
  98
  99         if (!vma || !vma->vm_file) {
 100                 return INVALID_COOKIE;
 101         }
 102         path = &vma->vm_file->f_path;
 103         if (!path || !path->dentry) {
 104                 return INVALID_COOKIE;
 105         }
 106
 107         text = (char*)path->dentry->d_name.name;
 108         if (per_cpu     (cookie_prev_text, cpu) == (uint32_t)text) {
 109                 return per_cpu(cookie_prev_value, cpu);
 110         }
 111
 112         key = gator_chksum_crc32(text);
 113         key = (key << 32) | (uint32_t)text;
 114
 115         cookie = cookiemap_exists(key);
 116         if (cookie) {
 117                 goto output;
 118         }
 119
 120         cookie = per_cpu(cookie_next_key, cpu)+=nr_cpu_ids;
 121         cookiemap_add(key, cookie);
 122
 123         gator_buffer_write_packed_int(cpu, PROTOCOL_COOKIE);
 124         gator_buffer_write_packed_int(cpu, cookie);
 125         gator_buffer_write_string(cpu, text);
 126
 127 output:
 128         per_cpu(cookie_prev_text, cpu) = (uint32_t)text;
 129         per_cpu(cookie_prev_value, cpu) = cookie;
 130         return cookie;
 131 }
 132
 133 static int get_exec_cookie(int cpu, struct task_struct *task)
 134 {
 135         unsigned long cookie = NO_COOKIE;
 136         struct mm_struct *mm = task->mm;
 137         struct vm_area_struct *vma;
 138
 139         if (!mm)
 140                 return cookie;
 141
 142         for (vma = mm->mmap; vma; vma = vma->vm_next) {
 143                 if (!vma->vm_file)
 144                         continue;
 145                 if (!(vma->vm_flags & VM_EXECUTABLE))
 146                         continue;
 147                 cookie = get_cookie(cpu, task->tgid, vma);
 148                 break;
 149         }
 150
 151         return cookie;
 152 }
 153
 154 static unsigned long get_address_cookie(int cpu, struct task_struct *task, unsigned long addr, off_t *offset)
 155 {
 156         unsigned long cookie = NO_COOKIE;
 157         struct mm_struct *mm = task->mm;
 158         struct vm_area_struct *vma;
 159
 160         if (!mm)
 161                 return cookie;
 162
 163         for (vma = find_vma(mm, addr); vma; vma = vma->vm_next) {
 164                 if (addr < vma->vm_start || addr >= vma->vm_end)
 165                         continue;
 166
 167                 if (vma->vm_file) {
 168                         cookie = get_cookie(cpu, task->tgid, vma);
 169                         *offset = (vma->vm_pgoff << PAGE_SHIFT) + addr - vma->vm_start;
 170                 } else {
 171                         /* must be an anonymous map */
 172                         *offset = addr;
 173                 }
 174
 175                 break;
 176         }
 177
 178         if (!vma)
 179                 cookie = INVALID_COOKIE;
 180
 181         return cookie;
 182 }
 183
 184 static void cookies_initialize(void)
 185 {
 186         uint32_t crc, poly;
 187         int cpu, size;
 188         int i, j;
 189
 190         for_each_possible_cpu(cpu) {
 191                 per_cpu(cookie_next_key, cpu) = nr_cpu_ids + cpu;
 192                 per_cpu(cookie_prev_text, cpu) = 0;
 193                 per_cpu(cookie_prev_value, cpu) = 0;
 194
 195                 size = COOKIEMAP_ENTRIES * MAX_COLLISIONS * sizeof(uint64_t);
 196                 per_cpu(cookie_keys, cpu) = (uint64_t*)kmalloc(size, GFP_KERNEL);
 197                 memset(per_cpu(cookie_keys, cpu), 0, size);
 198
 199                 size = COOKIEMAP_ENTRIES * MAX_COLLISIONS * sizeof(uint32_t);
 200                 per_cpu(cookie_values, cpu) = (uint32_t*)kmalloc(size, GFP_KERNEL);
 201                 memset(per_cpu(cookie_values, cpu), 0, size);
 202         }
 203
 204         // build CRC32 table
 205         poly = 0x04c11db7;
 206         gator_crc32_table = (uint32_t*)kmalloc(256 * sizeof(uint32_t), GFP_KERNEL);
 207         for (i = 0; i < 256; i++) {
 208                 crc = i;
 209                 for (j = 8; j > 0; j--) {
 210                         if (crc & 1) {
 211                                 crc = (crc >> 1) ^ poly;
 212                         } else {
 213                                 crc >>= 1;
 214                         }
 215                 }
 216                 gator_crc32_table[i] = crc;
 217         }
 218 }
 219
 220 static void cookies_release(void)
 221 {
 222         int cpu;
 223
 224         for_each_possible_cpu(cpu) {
 225                 kfree(per_cpu(cookie_keys, cpu));
 226                 per_cpu(cookie_keys, cpu) = NULL;
 227
 228                 kfree(per_cpu(cookie_values, cpu));
 229                 per_cpu(cookie_values, cpu) = NULL;
 230         }
 231
 232         kfree(gator_crc32_table);
 233         gator_crc32_table = NULL;
 234 }