image/sanitize.c

   1 /*
   2  * This program is free software; you can redistribute it and/or
   3  * modify it under the terms of the GNU General Public
   4  * License v2 as published by the Free Software Foundation.
   5  *
   6  * This program is distributed in the hope that it will be useful,
   7  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   8  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   9  * General Public License for more details.
  10  *
  11  * You should have received a copy of the GNU General Public
  12  * License along with this program; if not, write to the
  13  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  14  * Boston, MA 021110-1307, USA.
  15  */
  16
  17 #include "kerncompat.h"
  18 #include "internal.h"
  19 #include "messages.h"
  20 #include "utils.h"
  21 #include "kernel-lib/crc32c.h"
  22 #include "image/sanitize.h"
  23 #include "extent_io.h"
  24
  25 /*
  26  * Reverse CRC-32C table
  27  */
  28 static const u32 crc32c_rev_table[256] = {
  29         0x00000000L,0x05EC76F1L,0x0BD8EDE2L,0x0E349B13L,
  30         0x17B1DBC4L,0x125DAD35L,0x1C693626L,0x198540D7L,
  31         0x2F63B788L,0x2A8FC179L,0x24BB5A6AL,0x21572C9BL,
  32         0x38D26C4CL,0x3D3E1ABDL,0x330A81AEL,0x36E6F75FL,
  33         0x5EC76F10L,0x5B2B19E1L,0x551F82F2L,0x50F3F403L,
  34         0x4976B4D4L,0x4C9AC225L,0x42AE5936L,0x47422FC7L,
  35         0x71A4D898L,0x7448AE69L,0x7A7C357AL,0x7F90438BL,
  36         0x6615035CL,0x63F975ADL,0x6DCDEEBEL,0x6821984FL,
  37         0xBD8EDE20L,0xB862A8D1L,0xB65633C2L,0xB3BA4533L,
  38         0xAA3F05E4L,0xAFD37315L,0xA1E7E806L,0xA40B9EF7L,
  39         0x92ED69A8L,0x97011F59L,0x9935844AL,0x9CD9F2BBL,
  40         0x855CB26CL,0x80B0C49DL,0x8E845F8EL,0x8B68297FL,
  41         0xE349B130L,0xE6A5C7C1L,0xE8915CD2L,0xED7D2A23L,
  42         0xF4F86AF4L,0xF1141C05L,0xFF208716L,0xFACCF1E7L,
  43         0xCC2A06B8L,0xC9C67049L,0xC7F2EB5AL,0xC21E9DABL,
  44         0xDB9BDD7CL,0xDE77AB8DL,0xD043309EL,0xD5AF466FL,
  45         0x7EF1CAB1L,0x7B1DBC40L,0x75292753L,0x70C551A2L,
  46         0x69401175L,0x6CAC6784L,0x6298FC97L,0x67748A66L,
  47         0x51927D39L,0x547E0BC8L,0x5A4A90DBL,0x5FA6E62AL,
  48         0x4623A6FDL,0x43CFD00CL,0x4DFB4B1FL,0x48173DEEL,
  49         0x2036A5A1L,0x25DAD350L,0x2BEE4843L,0x2E023EB2L,
  50         0x37877E65L,0x326B0894L,0x3C5F9387L,0x39B3E576L,
  51         0x0F551229L,0x0AB964D8L,0x048DFFCBL,0x0161893AL,
  52         0x18E4C9EDL,0x1D08BF1CL,0x133C240FL,0x16D052FEL,
  53         0xC37F1491L,0xC6936260L,0xC8A7F973L,0xCD4B8F82L,
  54         0xD4CECF55L,0xD122B9A4L,0xDF1622B7L,0xDAFA5446L,
  55         0xEC1CA319L,0xE9F0D5E8L,0xE7C44EFBL,0xE228380AL,
  56         0xFBAD78DDL,0xFE410E2CL,0xF075953FL,0xF599E3CEL,
  57         0x9DB87B81L,0x98540D70L,0x96609663L,0x938CE092L,
  58         0x8A09A045L,0x8FE5D6B4L,0x81D14DA7L,0x843D3B56L,
  59         0xB2DBCC09L,0xB737BAF8L,0xB90321EBL,0xBCEF571AL,
  60         0xA56A17CDL,0xA086613CL,0xAEB2FA2FL,0xAB5E8CDEL,
  61         0xFDE39562L,0xF80FE393L,0xF63B7880L,0xF3D70E71L,
  62         0xEA524EA6L,0xEFBE3857L,0xE18AA344L,0xE466D5B5L,
  63         0xD28022EAL,0xD76C541BL,0xD958CF08L,0xDCB4B9F9L,
  64         0xC531F92EL,0xC0DD8FDFL,0xCEE914CCL,0xCB05623DL,
  65         0xA324FA72L,0xA6C88C83L,0xA8FC1790L,0xAD106161L,
  66         0xB49521B6L,0xB1795747L,0xBF4DCC54L,0xBAA1BAA5L,
  67         0x8C474DFAL,0x89AB3B0BL,0x879FA018L,0x8273D6E9L,
  68         0x9BF6963EL,0x9E1AE0CFL,0x902E7BDCL,0x95C20D2DL,
  69         0x406D4B42L,0x45813DB3L,0x4BB5A6A0L,0x4E59D051L,
  70         0x57DC9086L,0x5230E677L,0x5C047D64L,0x59E80B95L,
  71         0x6F0EFCCAL,0x6AE28A3BL,0x64D61128L,0x613A67D9L,
  72         0x78BF270EL,0x7D5351FFL,0x7367CAECL,0x768BBC1DL,
  73         0x1EAA2452L,0x1B4652A3L,0x1572C9B0L,0x109EBF41L,
  74         0x091BFF96L,0x0CF78967L,0x02C31274L,0x072F6485L,
  75         0x31C993DAL,0x3425E52BL,0x3A117E38L,0x3FFD08C9L,
  76         0x2678481EL,0x23943EEFL,0x2DA0A5FCL,0x284CD30DL,
  77         0x83125FD3L,0x86FE2922L,0x88CAB231L,0x8D26C4C0L,
  78         0x94A38417L,0x914FF2E6L,0x9F7B69F5L,0x9A971F04L,
  79         0xAC71E85BL,0xA99D9EAAL,0xA7A905B9L,0xA2457348L,
  80         0xBBC0339FL,0xBE2C456EL,0xB018DE7DL,0xB5F4A88CL,
  81         0xDDD530C3L,0xD8394632L,0xD60DDD21L,0xD3E1ABD0L,
  82         0xCA64EB07L,0xCF889DF6L,0xC1BC06E5L,0xC4507014L,
  83         0xF2B6874BL,0xF75AF1BAL,0xF96E6AA9L,0xFC821C58L,
  84         0xE5075C8FL,0xE0EB2A7EL,0xEEDFB16DL,0xEB33C79CL,
  85         0x3E9C81F3L,0x3B70F702L,0x35446C11L,0x30A81AE0L,
  86         0x292D5A37L,0x2CC12CC6L,0x22F5B7D5L,0x2719C124L,
  87         0x11FF367BL,0x1413408AL,0x1A27DB99L,0x1FCBAD68L,
  88         0x064EEDBFL,0x03A29B4EL,0x0D96005DL,0x087A76ACL,
  89         0x605BEEE3L,0x65B79812L,0x6B830301L,0x6E6F75F0L,
  90         0x77EA3527L,0x720643D6L,0x7C32D8C5L,0x79DEAE34L,
  91         0x4F38596BL,0x4AD42F9AL,0x44E0B489L,0x410CC278L,
  92         0x588982AFL,0x5D65F45EL,0x53516F4DL,0x56BD19BCL
  93 };
  94
  95 /*
  96  * Calculate a 4-byte suffix to match desired CRC32C
  97  *
  98  * @current_crc: CRC32C checksum of all bytes before the suffix
  99  * @desired_crc: the checksum that we want to get after adding the suffix
 100  *
 101  * Outputs: @suffix: pointer to where the suffix will be written (4-bytes)
 102  */
 103 static void find_collision_calc_suffix(unsigned long current_crc,
 104                                        unsigned long desired_crc,
 105                                        char *suffix)
 106 {
 107         int i;
 108
 109         for(i = 3; i >= 0; i--) {
 110                 desired_crc = (desired_crc << 8)
 111                             ^ crc32c_rev_table[desired_crc >> 24 & 0xFF]
 112                             ^ ((current_crc >> i * 8) & 0xFF);
 113         }
 114         for (i = 0; i < 4; i++)
 115                 suffix[i] = (desired_crc >> i * 8) & 0xFF;
 116 }
 117
 118 /*
 119  * Check if suffix is valid according to our file name conventions
 120  */
 121 static int find_collision_is_suffix_valid(const char *suffix)
 122 {
 123         int i;
 124         char c;
 125
 126         for (i = 0; i < 4; i++) {
 127                 c = suffix[i];
 128                 if (c < ' ' || c > 126 || c == '/')
 129                         return 0;
 130         }
 131         return 1;
 132 }
 133
 134 static int find_collision_reverse_crc32c(struct name *val, u32 name_len)
 135 {
 136         unsigned long checksum;
 137         unsigned long current_checksum;
 138         int found = 0;
 139         int i;
 140
 141         /* There are no same length collisions of 4 or less bytes */
 142         if (name_len <= 4)
 143                 return 0;
 144         checksum = crc32c(~1, val->val, name_len);
 145         name_len -= 4;
 146         memset(val->sub, ' ', name_len);
 147         i = 0;
 148         while (1) {
 149                 current_checksum = crc32c(~1, val->sub, name_len);
 150                 find_collision_calc_suffix(current_checksum,
 151                                            checksum,
 152                                            val->sub + name_len);
 153                 if (find_collision_is_suffix_valid(val->sub + name_len) &&
 154                     memcmp(val->sub, val->val, val->len)) {
 155                         found = 1;
 156                         break;
 157                 }
 158
 159                 if (val->sub[i] == 126) {
 160                         do {
 161                                 i++;
 162                                 if (i >= name_len)
 163                                         break;
 164                         } while (val->sub[i] == 126);
 165
 166                         if (i >= name_len)
 167                                 break;
 168                         val->sub[i]++;
 169                         if (val->sub[i] == '/')
 170                                 val->sub[i]++;
 171                         memset(val->sub, ' ', i);
 172                         i = 0;
 173                         continue;
 174                 } else {
 175                         val->sub[i]++;
 176                         if (val->sub[i] == '/')
 177                                 val->sub[i]++;
 178                 }
 179         }
 180         return found;
 181 }
 182
 183 static void tree_insert(struct rb_root *root, struct rb_node *ins,
 184                         int (*cmp)(struct rb_node *a, struct rb_node *b,
 185                                    int fuzz))
 186 {
 187         struct rb_node ** p = &root->rb_node;
 188         struct rb_node * parent = NULL;
 189         int dir;
 190
 191         while(*p) {
 192                 parent = *p;
 193
 194                 dir = cmp(*p, ins, 1);
 195                 if (dir < 0)
 196                         p = &(*p)->rb_left;
 197                 else if (dir > 0)
 198                         p = &(*p)->rb_right;
 199                 else
 200                         BUG();
 201         }
 202
 203         rb_link_node(ins, parent, p);
 204         rb_insert_color(ins, root);
 205 }
 206
 207 static struct rb_node *tree_search(struct rb_root *root,
 208                                    struct rb_node *search,
 209                                    int (*cmp)(struct rb_node *a,
 210                                               struct rb_node *b, int fuzz),
 211                                    int fuzz)
 212 {
 213         struct rb_node *n = root->rb_node;
 214         int dir;
 215
 216         while (n) {
 217                 dir = cmp(n, search, fuzz);
 218                 if (dir < 0)
 219                         n = n->rb_left;
 220                 else if (dir > 0)
 221                         n = n->rb_right;
 222                 else
 223                         return n;
 224         }
 225
 226         return NULL;
 227 }
 228
 229 static int name_cmp(struct rb_node *a, struct rb_node *b, int fuzz)
 230 {
 231         struct name *entry = rb_entry(a, struct name, n);
 232         struct name *ins = rb_entry(b, struct name, n);
 233         u32 len;
 234
 235         len = min(ins->len, entry->len);
 236         return memcmp(ins->val, entry->val, len);
 237 }
 238
 239 static char *find_collision(struct rb_root *name_tree, char *name,
 240                             u32 name_len)
 241 {
 242         struct name *val;
 243         struct rb_node *entry;
 244         struct name tmp;
 245         int found;
 246         int i;
 247
 248         tmp.val = name;
 249         tmp.len = name_len;
 250         entry = tree_search(name_tree, &tmp.n, name_cmp, 0);
 251         if (entry) {
 252                 val = rb_entry(entry, struct name, n);
 253                 free(name);
 254                 return val->sub;
 255         }
 256
 257         val = malloc(sizeof(struct name));
 258         if (!val) {
 259                 error("cannot sanitize name, not enough memory");
 260                 free(name);
 261                 return NULL;
 262         }
 263
 264         memset(val, 0, sizeof(*val));
 265
 266         val->val = name;
 267         val->len = name_len;
 268         val->sub = malloc(name_len);
 269         if (!val->sub) {
 270                 error("cannot sanitize name, not enough memory");
 271                 free(val);
 272                 free(name);
 273                 return NULL;
 274         }
 275
 276         found = find_collision_reverse_crc32c(val, name_len);
 277
 278         if (!found) {
 279                 warning(
 280 "cannot find a hash collision for '%.*s', generating garbage, it won't match indexes",
 281                         val->len, val->val);
 282                 for (i = 0; i < name_len; i++) {
 283                         char c = rand_range(94) + 33;
 284
 285                         if (c == '/')
 286                                 c++;
 287                         val->sub[i] = c;
 288                 }
 289         }
 290
 291         tree_insert(name_tree, &val->n, name_cmp);
 292         return val->sub;
 293 }
 294
 295 static char *generate_garbage(u32 name_len)
 296 {
 297         char *buf = malloc(name_len);
 298         int i;
 299
 300         if (!buf)
 301                 return NULL;
 302
 303         for (i = 0; i < name_len; i++) {
 304                 char c = rand_range(94) + 33;
 305
 306                 if (c == '/')
 307                         c++;
 308                 buf[i] = c;
 309         }
 310
 311         return buf;
 312 }
 313
 314 static void sanitize_dir_item(enum sanitize_mode sanitize,
 315                 struct rb_root *name_tree, struct extent_buffer *eb, int slot)
 316 {
 317         struct btrfs_dir_item *dir_item;
 318         char *buf;
 319         char *garbage;
 320         unsigned long name_ptr;
 321         u32 total_len;
 322         u32 cur = 0;
 323         u32 this_len;
 324         u32 name_len;
 325         int free_garbage = (sanitize == SANITIZE_NAMES);
 326
 327         dir_item = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
 328         total_len = btrfs_item_size_nr(eb, slot);
 329         while (cur < total_len) {
 330                 this_len = sizeof(*dir_item) +
 331                         btrfs_dir_name_len(eb, dir_item) +
 332                         btrfs_dir_data_len(eb, dir_item);
 333                 name_ptr = (unsigned long)(dir_item + 1);
 334                 name_len = btrfs_dir_name_len(eb, dir_item);
 335
 336                 if (sanitize == SANITIZE_COLLISIONS) {
 337                         buf = malloc(name_len);
 338                         if (!buf) {
 339                                 error("cannot sanitize name, not enough memory");
 340                                 return;
 341                         }
 342                         read_extent_buffer(eb, buf, name_ptr, name_len);
 343                         garbage = find_collision(name_tree, buf, name_len);
 344                 } else {
 345                         garbage = generate_garbage(name_len);
 346                 }
 347                 if (!garbage) {
 348                         error("cannot sanitize name, not enough memory");
 349                         return;
 350                 }
 351                 write_extent_buffer(eb, garbage, name_ptr, name_len);
 352                 cur += this_len;
 353                 dir_item = (struct btrfs_dir_item *)((char *)dir_item +
 354                                                      this_len);
 355                 if (free_garbage)
 356                         free(garbage);
 357         }
 358 }
 359
 360 static void sanitize_inode_ref(enum sanitize_mode sanitize,
 361                 struct rb_root *name_tree, struct extent_buffer *eb, int slot,
 362                 int ext)
 363 {
 364         struct btrfs_inode_extref *extref;
 365         struct btrfs_inode_ref *ref;
 366         char *garbage, *buf;
 367         unsigned long ptr;
 368         unsigned long name_ptr;
 369         u32 item_size;
 370         u32 cur_offset = 0;
 371         int len;
 372         int free_garbage = (sanitize == SANITIZE_NAMES);
 373
 374         item_size = btrfs_item_size_nr(eb, slot);
 375         ptr = btrfs_item_ptr_offset(eb, slot);
 376         while (cur_offset < item_size) {
 377                 if (ext) {
 378                         extref = (struct btrfs_inode_extref *)(ptr +
 379                                                                cur_offset);
 380                         name_ptr = (unsigned long)(&extref->name);
 381                         len = btrfs_inode_extref_name_len(eb, extref);
 382                         cur_offset += sizeof(*extref);
 383                 } else {
 384                         ref = (struct btrfs_inode_ref *)(ptr + cur_offset);
 385                         len = btrfs_inode_ref_name_len(eb, ref);
 386                         name_ptr = (unsigned long)(ref + 1);
 387                         cur_offset += sizeof(*ref);
 388                 }
 389                 cur_offset += len;
 390
 391                 if (sanitize == SANITIZE_COLLISIONS) {
 392                         buf = malloc(len);
 393                         if (!buf) {
 394                                 error("cannot sanitize name, not enough memory");
 395                                 return;
 396                         }
 397                         read_extent_buffer(eb, buf, name_ptr, len);
 398                         garbage = find_collision(name_tree, buf, len);
 399                 } else {
 400                         garbage = generate_garbage(len);
 401                 }
 402
 403                 if (!garbage) {
 404                         error("cannot sanitize name, not enough memory");
 405                         return;
 406                 }
 407                 write_extent_buffer(eb, garbage, name_ptr, len);
 408                 if (free_garbage)
 409                         free(garbage);
 410         }
 411 }
 412
 413 static void sanitize_xattr(struct extent_buffer *eb, int slot)
 414 {
 415         struct btrfs_dir_item *dir_item;
 416         unsigned long data_ptr;
 417         u32 data_len;
 418
 419         dir_item = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
 420         data_len = btrfs_dir_data_len(eb, dir_item);
 421
 422         data_ptr = (unsigned long)((char *)(dir_item + 1) +
 423                                    btrfs_dir_name_len(eb, dir_item));
 424         memset_extent_buffer(eb, 0, data_ptr, data_len);
 425 }
 426
 427 static struct extent_buffer *alloc_dummy_eb(u64 bytenr, u32 size)
 428 {
 429         struct extent_buffer *eb;
 430
 431         eb = calloc(1, sizeof(struct extent_buffer) + size);
 432         if (!eb)
 433                 return NULL;
 434
 435         eb->start = bytenr;
 436         eb->len = size;
 437         return eb;
 438 }
 439
 440 void sanitize_name(enum sanitize_mode sanitize, struct rb_root *name_tree,
 441                 u8 *dst, struct extent_buffer *src, struct btrfs_key *key,
 442                 int slot)
 443 {
 444         struct extent_buffer *eb;
 445
 446         eb = alloc_dummy_eb(src->start, src->len);
 447         if (!eb) {
 448                 error("cannot sanitize name, not enough memory");
 449                 return;
 450         }
 451
 452         memcpy(eb->data, src->data, src->len);
 453
 454         switch (key->type) {
 455         case BTRFS_DIR_ITEM_KEY:
 456         case BTRFS_DIR_INDEX_KEY:
 457                 sanitize_dir_item(sanitize, name_tree, eb, slot);
 458                 break;
 459         case BTRFS_INODE_REF_KEY:
 460                 sanitize_inode_ref(sanitize, name_tree, eb, slot, 0);
 461                 break;
 462         case BTRFS_INODE_EXTREF_KEY:
 463                 sanitize_inode_ref(sanitize, name_tree, eb, slot, 1);
 464                 break;
 465         case BTRFS_XATTR_ITEM_KEY:
 466                 sanitize_xattr(eb, slot);
 467                 break;
 468         default:
 469                 break;
 470         }
 471
 472         memcpy(dst, eb->data, eb->len);
 473         free(eb);
 474 }
 475