← Back to branch summary

~ubuntu-branches/debian/jessie/btrfs-tools/jessie

« back to all changes in this revision

Viewing changes to .pc/0003-Fixing-unaligned-memory-accesses.patch/volumes.c

  • Committer: Package Import Robot
  • Author(s): Dimitri John Ledkov
  • Date: 2014-04-19 12:12:11 UTC
  • mfrom: (1.2.12) (6.1.37 sid)
  • Revision ID: package-import@ubuntu.com-20140419121211-mski0g757tsdv4x1
Tags: 3.14.1-1
* New upstream release.
* Switch to git-dpm.
* Rebase and cleanup patches.

Show diffs side-by-side

added added

removed removed

Lines of Context:
.pc/0003-Fixing-unaligned-memory-accesses.patch/volumes.c
 
1
/*
 
2
 * Copyright (C) 2007 Oracle.  All rights reserved.
 
3
 *
 
4
 * This program is free software; you can redistribute it and/or
 
5
 * modify it under the terms of the GNU General Public
 
6
 * License v2 as published by the Free Software Foundation.
 
7
 *
 
8
 * This program is distributed in the hope that it will be useful,
 
9
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
11
 * General Public License for more details.
 
12
 *
 
13
 * You should have received a copy of the GNU General Public
 
14
 * License along with this program; if not, write to the
 
15
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 
16
 * Boston, MA 021110-1307, USA.
 
17
 */
 
18
#define _XOPEN_SOURCE 600
 
19
#define __USE_XOPEN2K
 
20
#include <stdio.h>
 
21
#include <stdlib.h>
 
22
#include <sys/types.h>
 
23
#include <sys/stat.h>
 
24
#include <uuid/uuid.h>
 
25
#include <fcntl.h>
 
26
#include <unistd.h>
 
27
#include "ctree.h"
 
28
#include "disk-io.h"
 
29
#include "transaction.h"
 
30
#include "print-tree.h"
 
31
#include "volumes.h"
 
32
#include "math.h"
 
33
 
 
34
struct stripe {
 
35
        struct btrfs_device *dev;
 
36
        u64 physical;
 
37
};
 
38
 
 
39
static inline int nr_parity_stripes(struct map_lookup *map)
 
40
{
 
41
        if (map->type & BTRFS_BLOCK_GROUP_RAID5)
 
42
                return 1;
 
43
        else if (map->type & BTRFS_BLOCK_GROUP_RAID6)
 
44
                return 2;
 
45
        else
 
46
                return 0;
 
47
}
 
48
 
 
49
static inline int nr_data_stripes(struct map_lookup *map)
 
50
{
 
51
        return map->num_stripes - nr_parity_stripes(map);
 
52
}
 
53
 
 
54
#define is_parity_stripe(x) ( ((x) == BTRFS_RAID5_P_STRIPE) || ((x) == BTRFS_RAID6_Q_STRIPE) )
 
55
 
 
56
static LIST_HEAD(fs_uuids);
 
57
 
 
58
static struct btrfs_device *__find_device(struct list_head *head, u64 devid,
 
59
                                          u8 *uuid)
 
60
{
 
61
        struct btrfs_device *dev;
 
62
        struct list_head *cur;
 
63
 
 
64
        list_for_each(cur, head) {
 
65
                dev = list_entry(cur, struct btrfs_device, dev_list);
 
66
                if (dev->devid == devid &&
 
67
                    !memcmp(dev->uuid, uuid, BTRFS_UUID_SIZE)) {
 
68
                        return dev;
 
69
                }
 
70
        }
 
71
        return NULL;
 
72
}
 
73
 
 
74
static struct btrfs_fs_devices *find_fsid(u8 *fsid)
 
75
{
 
76
        struct list_head *cur;
 
77
        struct btrfs_fs_devices *fs_devices;
 
78
 
 
79
        list_for_each(cur, &fs_uuids) {
 
80
                fs_devices = list_entry(cur, struct btrfs_fs_devices, list);
 
81
                if (memcmp(fsid, fs_devices->fsid, BTRFS_FSID_SIZE) == 0)
 
82
                        return fs_devices;
 
83
        }
 
84
        return NULL;
 
85
}
 
86
 
 
87
static int device_list_add(const char *path,
 
88
                           struct btrfs_super_block *disk_super,
 
89
                           u64 devid, struct btrfs_fs_devices **fs_devices_ret)
 
90
{
 
91
        struct btrfs_device *device;
 
92
        struct btrfs_fs_devices *fs_devices;
 
93
        u64 found_transid = btrfs_super_generation(disk_super);
 
94
 
 
95
        fs_devices = find_fsid(disk_super->fsid);
 
96
        if (!fs_devices) {
 
97
                fs_devices = kzalloc(sizeof(*fs_devices), GFP_NOFS);
 
98
                if (!fs_devices)
 
99
                        return -ENOMEM;
 
100
                INIT_LIST_HEAD(&fs_devices->devices);
 
101
                list_add(&fs_devices->list, &fs_uuids);
 
102
                memcpy(fs_devices->fsid, disk_super->fsid, BTRFS_FSID_SIZE);
 
103
                fs_devices->latest_devid = devid;
 
104
                fs_devices->latest_trans = found_transid;
 
105
                fs_devices->lowest_devid = (u64)-1;
 
106
                device = NULL;
 
107
        } else {
 
108
                device = __find_device(&fs_devices->devices, devid,
 
109
                                       disk_super->dev_item.uuid);
 
110
        }
 
111
        if (!device) {
 
112
                device = kzalloc(sizeof(*device), GFP_NOFS);
 
113
                if (!device) {
 
114
                        /* we can safely leave the fs_devices entry around */
 
115
                        return -ENOMEM;
 
116
                }
 
117
                device->fd = -1;
 
118
                device->devid = devid;
 
119
                memcpy(device->uuid, disk_super->dev_item.uuid,
 
120
                       BTRFS_UUID_SIZE);
 
121
                device->name = kstrdup(path, GFP_NOFS);
 
122
                if (!device->name) {
 
123
                        kfree(device);
 
124
                        return -ENOMEM;
 
125
                }
 
126
                device->label = kstrdup(disk_super->label, GFP_NOFS);
 
127
                if (!device->label) {
 
128
                        kfree(device->name);
 
129
                        kfree(device);
 
130
                        return -ENOMEM;
 
131
                }
 
132
                device->total_devs = btrfs_super_num_devices(disk_super);
 
133
                device->super_bytes_used = btrfs_super_bytes_used(disk_super);
 
134
                device->total_bytes =
 
135
                        btrfs_stack_device_total_bytes(&disk_super->dev_item);
 
136
                device->bytes_used =
 
137
                        btrfs_stack_device_bytes_used(&disk_super->dev_item);
 
138
                list_add(&device->dev_list, &fs_devices->devices);
 
139
                device->fs_devices = fs_devices;
 
140
        } else if (!device->name || strcmp(device->name, path)) {
 
141
                char *name = strdup(path);
 
142
                if (!name)
 
143
                        return -ENOMEM;
 
144
                kfree(device->name);
 
145
                device->name = name;
 
146
        }
 
147
 
 
148
 
 
149
        if (found_transid > fs_devices->latest_trans) {
 
150
                fs_devices->latest_devid = devid;
 
151
                fs_devices->latest_trans = found_transid;
 
152
        }
 
153
        if (fs_devices->lowest_devid > devid) {
 
154
                fs_devices->lowest_devid = devid;
 
155
        }
 
156
        *fs_devices_ret = fs_devices;
 
157
        return 0;
 
158
}
 
159
 
 
160
int btrfs_close_devices(struct btrfs_fs_devices *fs_devices)
 
161
{
 
162
        struct btrfs_fs_devices *seed_devices;
 
163
        struct btrfs_device *device;
 
164
 
 
165
again:
 
166
        while (!list_empty(&fs_devices->devices)) {
 
167
                device = list_entry(fs_devices->devices.next,
 
168
                                    struct btrfs_device, dev_list);
 
169
                if (device->fd != -1) {
 
170
                        fsync(device->fd);
 
171
                        if (posix_fadvise(device->fd, 0, 0, POSIX_FADV_DONTNEED))
 
172
                                fprintf(stderr, "Warning, could not drop caches\n");
 
173
                        close(device->fd);
 
174
                        device->fd = -1;
 
175
                }
 
176
                device->writeable = 0;
 
177
                list_del(&device->dev_list);
 
178
                /* free the memory */
 
179
                free(device->name);
 
180
                free(device->label);
 
181
                free(device);
 
182
        }
 
183
 
 
184
        seed_devices = fs_devices->seed;
 
185
        fs_devices->seed = NULL;
 
186
        if (seed_devices) {
 
187
                fs_devices = seed_devices;
 
188
                goto again;
 
189
        }
 
190
 
 
191
        free(fs_devices);
 
192
        return 0;
 
193
}
 
194
 
 
195
int btrfs_open_devices(struct btrfs_fs_devices *fs_devices, int flags)
 
196
{
 
197
        int fd;
 
198
        struct list_head *head = &fs_devices->devices;
 
199
        struct list_head *cur;
 
200
        struct btrfs_device *device;
 
201
        int ret;
 
202
 
 
203
        list_for_each(cur, head) {
 
204
                device = list_entry(cur, struct btrfs_device, dev_list);
 
205
                if (!device->name) {
 
206
                        printk("no name for device %llu, skip it now\n", device->devid);
 
207
                        continue;
 
208
                }
 
209
 
 
210
                fd = open(device->name, flags);
 
211
                if (fd < 0) {
 
212
                        ret = -errno;
 
213
                        goto fail;
 
214
                }
 
215
 
 
216
                if (posix_fadvise(fd, 0, 0, POSIX_FADV_DONTNEED))
 
217
                        fprintf(stderr, "Warning, could not drop caches\n");
 
218
 
 
219
                if (device->devid == fs_devices->latest_devid)
 
220
                        fs_devices->latest_bdev = fd;
 
221
                if (device->devid == fs_devices->lowest_devid)
 
222
                        fs_devices->lowest_bdev = fd;
 
223
                device->fd = fd;
 
224
                if (flags & O_RDWR)
 
225
                        device->writeable = 1;
 
226
        }
 
227
        return 0;
 
228
fail:
 
229
        btrfs_close_devices(fs_devices);
 
230
        return ret;
 
231
}
 
232
 
 
233
int btrfs_scan_one_device(int fd, const char *path,
 
234
                          struct btrfs_fs_devices **fs_devices_ret,
 
235
                          u64 *total_devs, u64 super_offset)
 
236
{
 
237
        struct btrfs_super_block *disk_super;
 
238
        char *buf;
 
239
        int ret;
 
240
        u64 devid;
 
241
 
 
242
        buf = malloc(4096);
 
243
        if (!buf) {
 
244
                ret = -ENOMEM;
 
245
                goto error;
 
246
        }
 
247
        disk_super = (struct btrfs_super_block *)buf;
 
248
        ret = btrfs_read_dev_super(fd, disk_super, super_offset);
 
249
        if (ret < 0) {
 
250
                ret = -EIO;
 
251
                goto error_brelse;
 
252
        }
 
253
        devid = btrfs_stack_device_id(&disk_super->dev_item);
 
254
        if (btrfs_super_flags(disk_super) & BTRFS_SUPER_FLAG_METADUMP)
 
255
                *total_devs = 1;
 
256
        else
 
257
                *total_devs = btrfs_super_num_devices(disk_super);
 
258
 
 
259
        ret = device_list_add(path, disk_super, devid, fs_devices_ret);
 
260
 
 
261
error_brelse:
 
262
        free(buf);
 
263
error:
 
264
        return ret;
 
265
}
 
266
 
 
267
/*
 
268
 * this uses a pretty simple search, the expectation is that it is
 
269
 * called very infrequently and that a given device has a small number
 
270
 * of extents
 
271
 */
 
272
static int find_free_dev_extent(struct btrfs_trans_handle *trans,
 
273
                                struct btrfs_device *device,
 
274
                                struct btrfs_path *path,
 
275
                                u64 num_bytes, u64 *start)
 
276
{
 
277
        struct btrfs_key key;
 
278
        struct btrfs_root *root = device->dev_root;
 
279
        struct btrfs_dev_extent *dev_extent = NULL;
 
280
        u64 hole_size = 0;
 
281
        u64 last_byte = 0;
 
282
        u64 search_start = root->fs_info->alloc_start;
 
283
        u64 search_end = device->total_bytes;
 
284
        int ret;
 
285
        int slot = 0;
 
286
        int start_found;
 
287
        struct extent_buffer *l;
 
288
 
 
289
        start_found = 0;
 
290
        path->reada = 2;
 
291
 
 
292
        /* FIXME use last free of some kind */
 
293
 
 
294
        /* we don't want to overwrite the superblock on the drive,
 
295
         * so we make sure to start at an offset of at least 1MB
 
296
         */
 
297
        search_start = max(BTRFS_BLOCK_RESERVED_1M_FOR_SUPER, search_start);
 
298
 
 
299
        if (search_start >= search_end) {
 
300
                ret = -ENOSPC;
 
301
                goto error;
 
302
        }
 
303
 
 
304
        key.objectid = device->devid;
 
305
        key.offset = search_start;
 
306
        key.type = BTRFS_DEV_EXTENT_KEY;
 
307
        ret = btrfs_search_slot(trans, root, &key, path, 0, 0);
 
308
        if (ret < 0)
 
309
                goto error;
 
310
        ret = btrfs_previous_item(root, path, 0, key.type);
 
311
        if (ret < 0)
 
312
                goto error;
 
313
        l = path->nodes[0];
 
314
        btrfs_item_key_to_cpu(l, &key, path->slots[0]);
 
315
        while (1) {
 
316
                l = path->nodes[0];
 
317
                slot = path->slots[0];
 
318
                if (slot >= btrfs_header_nritems(l)) {
 
319
                        ret = btrfs_next_leaf(root, path);
 
320
                        if (ret == 0)
 
321
                                continue;
 
322
                        if (ret < 0)
 
323
                                goto error;
 
324
no_more_items:
 
325
                        if (!start_found) {
 
326
                                if (search_start >= search_end) {
 
327
                                        ret = -ENOSPC;
 
328
                                        goto error;
 
329
                                }
 
330
                                *start = search_start;
 
331
                                start_found = 1;
 
332
                                goto check_pending;
 
333
                        }
 
334
                        *start = last_byte > search_start ?
 
335
                                last_byte : search_start;
 
336
                        if (search_end <= *start) {
 
337
                                ret = -ENOSPC;
 
338
                                goto error;
 
339
                        }
 
340
                        goto check_pending;
 
341
                }
 
342
                btrfs_item_key_to_cpu(l, &key, slot);
 
343
 
 
344
                if (key.objectid < device->devid)
 
345
                        goto next;
 
346
 
 
347
                if (key.objectid > device->devid)
 
348
                        goto no_more_items;
 
349
 
 
350
                if (key.offset >= search_start && key.offset > last_byte &&
 
351
                    start_found) {
 
352
                        if (last_byte < search_start)
 
353
                                last_byte = search_start;
 
354
                        hole_size = key.offset - last_byte;
 
355
                        if (key.offset > last_byte &&
 
356
                            hole_size >= num_bytes) {
 
357
                                *start = last_byte;
 
358
                                goto check_pending;
 
359
                        }
 
360
                }
 
361
                if (btrfs_key_type(&key) != BTRFS_DEV_EXTENT_KEY) {
 
362
                        goto next;
 
363
                }
 
364
 
 
365
                start_found = 1;
 
366
                dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
 
367
                last_byte = key.offset + btrfs_dev_extent_length(l, dev_extent);
 
368
next:
 
369
                path->slots[0]++;
 
370
                cond_resched();
 
371
        }
 
372
check_pending:
 
373
        /* we have to make sure we didn't find an extent that has already
 
374
         * been allocated by the map tree or the original allocation
 
375
         */
 
376
        btrfs_release_path(path);
 
377
        BUG_ON(*start < search_start);
 
378
 
 
379
        if (*start + num_bytes > search_end) {
 
380
                ret = -ENOSPC;
 
381
                goto error;
 
382
        }
 
383
        /* check for pending inserts here */
 
384
        return 0;
 
385
 
 
386
error:
 
387
        btrfs_release_path(path);
 
388
        return ret;
 
389
}
 
390
 
 
391
static int btrfs_alloc_dev_extent(struct btrfs_trans_handle *trans,
 
392
                                  struct btrfs_device *device,
 
393
                                  u64 chunk_tree, u64 chunk_objectid,
 
394
                                  u64 chunk_offset,
 
395
                                  u64 num_bytes, u64 *start)
 
396
{
 
397
        int ret;
 
398
        struct btrfs_path *path;
 
399
        struct btrfs_root *root = device->dev_root;
 
400
        struct btrfs_dev_extent *extent;
 
401
        struct extent_buffer *leaf;
 
402
        struct btrfs_key key;
 
403
 
 
404
        path = btrfs_alloc_path();
 
405
        if (!path)
 
406
                return -ENOMEM;
 
407
 
 
408
        ret = find_free_dev_extent(trans, device, path, num_bytes, start);
 
409
        if (ret) {
 
410
                goto err;
 
411
        }
 
412
 
 
413
        key.objectid = device->devid;
 
414
        key.offset = *start;
 
415
        key.type = BTRFS_DEV_EXTENT_KEY;
 
416
        ret = btrfs_insert_empty_item(trans, root, path, &key,
 
417
                                      sizeof(*extent));
 
418
        BUG_ON(ret);
 
419
 
 
420
        leaf = path->nodes[0];
 
421
        extent = btrfs_item_ptr(leaf, path->slots[0],
 
422
                                struct btrfs_dev_extent);
 
423
        btrfs_set_dev_extent_chunk_tree(leaf, extent, chunk_tree);
 
424
        btrfs_set_dev_extent_chunk_objectid(leaf, extent, chunk_objectid);
 
425
        btrfs_set_dev_extent_chunk_offset(leaf, extent, chunk_offset);
 
426
 
 
427
        write_extent_buffer(leaf, root->fs_info->chunk_tree_uuid,
 
428
                    (unsigned long)btrfs_dev_extent_chunk_tree_uuid(extent),
 
429
                    BTRFS_UUID_SIZE);
 
430
 
 
431
        btrfs_set_dev_extent_length(leaf, extent, num_bytes);
 
432
        btrfs_mark_buffer_dirty(leaf);
 
433
err:
 
434
        btrfs_free_path(path);
 
435
        return ret;
 
436
}
 
437
 
 
438
static int find_next_chunk(struct btrfs_root *root, u64 objectid, u64 *offset)
 
439
{
 
440
        struct btrfs_path *path;
 
441
        int ret;
 
442
        struct btrfs_key key;
 
443
        struct btrfs_chunk *chunk;
 
444
        struct btrfs_key found_key;
 
445
 
 
446
        path = btrfs_alloc_path();
 
447
        BUG_ON(!path);
 
448
 
 
449
        key.objectid = objectid;
 
450
        key.offset = (u64)-1;
 
451
        key.type = BTRFS_CHUNK_ITEM_KEY;
 
452
 
 
453
        ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 
454
        if (ret < 0)
 
455
                goto error;
 
456
 
 
457
        BUG_ON(ret == 0);
 
458
 
 
459
        ret = btrfs_previous_item(root, path, 0, BTRFS_CHUNK_ITEM_KEY);
 
460
        if (ret) {
 
461
                *offset = 0;
 
462
        } else {
 
463
                btrfs_item_key_to_cpu(path->nodes[0], &found_key,
 
464
                                      path->slots[0]);
 
465
                if (found_key.objectid != objectid)
 
466
                        *offset = 0;
 
467
                else {
 
468
                        chunk = btrfs_item_ptr(path->nodes[0], path->slots[0],
 
469
                                               struct btrfs_chunk);
 
470
                        *offset = found_key.offset +
 
471
                                btrfs_chunk_length(path->nodes[0], chunk);
 
472
                }
 
473
        }
 
474
        ret = 0;
 
475
error:
 
476
        btrfs_free_path(path);
 
477
        return ret;
 
478
}
 
479
 
 
480
static int find_next_devid(struct btrfs_root *root, struct btrfs_path *path,
 
481
                           u64 *objectid)
 
482
{
 
483
        int ret;
 
484
        struct btrfs_key key;
 
485
        struct btrfs_key found_key;
 
486
 
 
487
        key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 
488
        key.type = BTRFS_DEV_ITEM_KEY;
 
489
        key.offset = (u64)-1;
 
490
 
 
491
        ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 
492
        if (ret < 0)
 
493
                goto error;
 
494
 
 
495
        BUG_ON(ret == 0);
 
496
 
 
497
        ret = btrfs_previous_item(root, path, BTRFS_DEV_ITEMS_OBJECTID,
 
498
                                  BTRFS_DEV_ITEM_KEY);
 
499
        if (ret) {
 
500
                *objectid = 1;
 
501
        } else {
 
502
                btrfs_item_key_to_cpu(path->nodes[0], &found_key,
 
503
                                      path->slots[0]);
 
504
                *objectid = found_key.offset + 1;
 
505
        }
 
506
        ret = 0;
 
507
error:
 
508
        btrfs_release_path(path);
 
509
        return ret;
 
510
}
 
511
 
 
512
/*
 
513
 * the device information is stored in the chunk root
 
514
 * the btrfs_device struct should be fully filled in
 
515
 */
 
516
int btrfs_add_device(struct btrfs_trans_handle *trans,
 
517
                     struct btrfs_root *root,
 
518
                     struct btrfs_device *device)
 
519
{
 
520
        int ret;
 
521
        struct btrfs_path *path;
 
522
        struct btrfs_dev_item *dev_item;
 
523
        struct extent_buffer *leaf;
 
524
        struct btrfs_key key;
 
525
        unsigned long ptr;
 
526
        u64 free_devid = 0;
 
527
 
 
528
        root = root->fs_info->chunk_root;
 
529
 
 
530
        path = btrfs_alloc_path();
 
531
        if (!path)
 
532
                return -ENOMEM;
 
533
 
 
534
        ret = find_next_devid(root, path, &free_devid);
 
535
        if (ret)
 
536
                goto out;
 
537
 
 
538
        key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 
539
        key.type = BTRFS_DEV_ITEM_KEY;
 
540
        key.offset = free_devid;
 
541
 
 
542
        ret = btrfs_insert_empty_item(trans, root, path, &key,
 
543
                                      sizeof(*dev_item));
 
544
        if (ret)
 
545
                goto out;
 
546
 
 
547
        leaf = path->nodes[0];
 
548
        dev_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_item);
 
549
 
 
550
        device->devid = free_devid;
 
551
        btrfs_set_device_id(leaf, dev_item, device->devid);
 
552
        btrfs_set_device_generation(leaf, dev_item, 0);
 
553
        btrfs_set_device_type(leaf, dev_item, device->type);
 
554
        btrfs_set_device_io_align(leaf, dev_item, device->io_align);
 
555
        btrfs_set_device_io_width(leaf, dev_item, device->io_width);
 
556
        btrfs_set_device_sector_size(leaf, dev_item, device->sector_size);
 
557
        btrfs_set_device_total_bytes(leaf, dev_item, device->total_bytes);
 
558
        btrfs_set_device_bytes_used(leaf, dev_item, device->bytes_used);
 
559
        btrfs_set_device_group(leaf, dev_item, 0);
 
560
        btrfs_set_device_seek_speed(leaf, dev_item, 0);
 
561
        btrfs_set_device_bandwidth(leaf, dev_item, 0);
 
562
        btrfs_set_device_start_offset(leaf, dev_item, 0);
 
563
 
 
564
        ptr = (unsigned long)btrfs_device_uuid(dev_item);
 
565
        write_extent_buffer(leaf, device->uuid, ptr, BTRFS_UUID_SIZE);
 
566
        ptr = (unsigned long)btrfs_device_fsid(dev_item);
 
567
        write_extent_buffer(leaf, root->fs_info->fsid, ptr, BTRFS_UUID_SIZE);
 
568
        btrfs_mark_buffer_dirty(leaf);
 
569
        ret = 0;
 
570
 
 
571
out:
 
572
        btrfs_free_path(path);
 
573
        return ret;
 
574
}
 
575
 
 
576
int btrfs_update_device(struct btrfs_trans_handle *trans,
 
577
                        struct btrfs_device *device)
 
578
{
 
579
        int ret;
 
580
        struct btrfs_path *path;
 
581
        struct btrfs_root *root;
 
582
        struct btrfs_dev_item *dev_item;
 
583
        struct extent_buffer *leaf;
 
584
        struct btrfs_key key;
 
585
 
 
586
        root = device->dev_root->fs_info->chunk_root;
 
587
 
 
588
        path = btrfs_alloc_path();
 
589
        if (!path)
 
590
                return -ENOMEM;
 
591
 
 
592
        key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 
593
        key.type = BTRFS_DEV_ITEM_KEY;
 
594
        key.offset = device->devid;
 
595
 
 
596
        ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 
597
        if (ret < 0)
 
598
                goto out;
 
599
 
 
600
        if (ret > 0) {
 
601
                ret = -ENOENT;
 
602
                goto out;
 
603
        }
 
604
 
 
605
        leaf = path->nodes[0];
 
606
        dev_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_item);
 
607
 
 
608
        btrfs_set_device_id(leaf, dev_item, device->devid);
 
609
        btrfs_set_device_type(leaf, dev_item, device->type);
 
610
        btrfs_set_device_io_align(leaf, dev_item, device->io_align);
 
611
        btrfs_set_device_io_width(leaf, dev_item, device->io_width);
 
612
        btrfs_set_device_sector_size(leaf, dev_item, device->sector_size);
 
613
        btrfs_set_device_total_bytes(leaf, dev_item, device->total_bytes);
 
614
        btrfs_set_device_bytes_used(leaf, dev_item, device->bytes_used);
 
615
        btrfs_mark_buffer_dirty(leaf);
 
616
 
 
617
out:
 
618
        btrfs_free_path(path);
 
619
        return ret;
 
620
}
 
621
 
 
622
int btrfs_add_system_chunk(struct btrfs_trans_handle *trans,
 
623
                           struct btrfs_root *root,
 
624
                           struct btrfs_key *key,
 
625
                           struct btrfs_chunk *chunk, int item_size)
 
626
{
 
627
        struct btrfs_super_block *super_copy = root->fs_info->super_copy;
 
628
        struct btrfs_disk_key disk_key;
 
629
        u32 array_size;
 
630
        u8 *ptr;
 
631
 
 
632
        array_size = btrfs_super_sys_array_size(super_copy);
 
633
        if (array_size + item_size > BTRFS_SYSTEM_CHUNK_ARRAY_SIZE)
 
634
                return -EFBIG;
 
635
 
 
636
        ptr = super_copy->sys_chunk_array + array_size;
 
637
        btrfs_cpu_key_to_disk(&disk_key, key);
 
638
        memcpy(ptr, &disk_key, sizeof(disk_key));
 
639
        ptr += sizeof(disk_key);
 
640
        memcpy(ptr, chunk, item_size);
 
641
        item_size += sizeof(disk_key);
 
642
        btrfs_set_super_sys_array_size(super_copy, array_size + item_size);
 
643
        return 0;
 
644
}
 
645
 
 
646
static u64 chunk_bytes_by_type(u64 type, u64 calc_size, int num_stripes,
 
647
                               int sub_stripes)
 
648
{
 
649
        if (type & (BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_DUP))
 
650
                return calc_size;
 
651
        else if (type & BTRFS_BLOCK_GROUP_RAID10)
 
652
                return calc_size * (num_stripes / sub_stripes);
 
653
        else if (type & BTRFS_BLOCK_GROUP_RAID5)
 
654
                return calc_size * (num_stripes - 1);
 
655
        else if (type & BTRFS_BLOCK_GROUP_RAID6)
 
656
                return calc_size * (num_stripes - 2);
 
657
        else
 
658
                return calc_size * num_stripes;
 
659
}
 
660
 
 
661
 
 
662
static u32 find_raid56_stripe_len(u32 data_devices, u32 dev_stripe_target)
 
663
{
 
664
        /* TODO, add a way to store the preferred stripe size */
 
665
        return BTRFS_STRIPE_LEN;
 
666
}
 
667
 
 
668
/*
 
669
 * btrfs_device_avail_bytes - count bytes available for alloc_chunk
 
670
 *
 
671
 * It is not equal to "device->total_bytes - device->bytes_used".
 
672
 * We do not allocate any chunk in 1M at beginning of device, and not
 
673
 * allowed to allocate any chunk before alloc_start if it is specified.
 
674
 * So search holes from max(1M, alloc_start) to device->total_bytes.
 
675
 */
 
676
static int btrfs_device_avail_bytes(struct btrfs_trans_handle *trans,
 
677
                                    struct btrfs_device *device,
 
678
                                    u64 *avail_bytes)
 
679
{
 
680
        struct btrfs_path *path;
 
681
        struct btrfs_root *root = device->dev_root;
 
682
        struct btrfs_key key;
 
683
        struct btrfs_dev_extent *dev_extent = NULL;
 
684
        struct extent_buffer *l;
 
685
        u64 search_start = root->fs_info->alloc_start;
 
686
        u64 search_end = device->total_bytes;
 
687
        u64 extent_end = 0;
 
688
        u64 free_bytes = 0;
 
689
        int ret;
 
690
        int slot = 0;
 
691
 
 
692
        search_start = max(BTRFS_BLOCK_RESERVED_1M_FOR_SUPER, search_start);
 
693
 
 
694
        path = btrfs_alloc_path();
 
695
        if (!path)
 
696
                return -ENOMEM;
 
697
 
 
698
        key.objectid = device->devid;
 
699
        key.offset = root->fs_info->alloc_start;
 
700
        key.type = BTRFS_DEV_EXTENT_KEY;
 
701
 
 
702
        path->reada = 2;
 
703
        ret = btrfs_search_slot(trans, root, &key, path, 0, 0);
 
704
        if (ret < 0)
 
705
                goto error;
 
706
        ret = btrfs_previous_item(root, path, 0, key.type);
 
707
        if (ret < 0)
 
708
                goto error;
 
709
 
 
710
        while (1) {
 
711
                l = path->nodes[0];
 
712
                slot = path->slots[0];
 
713
                if (slot >= btrfs_header_nritems(l)) {
 
714
                        ret = btrfs_next_leaf(root, path);
 
715
                        if (ret == 0)
 
716
                                continue;
 
717
                        if (ret < 0)
 
718
                                goto error;
 
719
                        break;
 
720
                }
 
721
                btrfs_item_key_to_cpu(l, &key, slot);
 
722
 
 
723
                if (key.objectid < device->devid)
 
724
                        goto next;
 
725
                if (key.objectid > device->devid)
 
726
                        break;
 
727
                if (btrfs_key_type(&key) != BTRFS_DEV_EXTENT_KEY)
 
728
                        goto next;
 
729
                if (key.offset > search_end)
 
730
                        break;
 
731
                if (key.offset > search_start)
 
732
                        free_bytes += key.offset - search_start;
 
733
 
 
734
                dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
 
735
                extent_end = key.offset + btrfs_dev_extent_length(l,
 
736
                                                                  dev_extent);
 
737
                if (extent_end > search_start)
 
738
                        search_start = extent_end;
 
739
                if (search_start > search_end)
 
740
                        break;
 
741
next:
 
742
                path->slots[0]++;
 
743
                cond_resched();
 
744
        }
 
745
 
 
746
        if (search_start < search_end)
 
747
                free_bytes += search_end - search_start;
 
748
 
 
749
        *avail_bytes = free_bytes;
 
750
        ret = 0;
 
751
error:
 
752
        btrfs_free_path(path);
 
753
        return ret;
 
754
}
 
755
 
 
756
int btrfs_alloc_chunk(struct btrfs_trans_handle *trans,
 
757
                      struct btrfs_root *extent_root, u64 *start,
 
758
                      u64 *num_bytes, u64 type)
 
759
{
 
760
        u64 dev_offset;
 
761
        struct btrfs_fs_info *info = extent_root->fs_info;
 
762
        struct btrfs_root *chunk_root = info->chunk_root;
 
763
        struct btrfs_stripe *stripes;
 
764
        struct btrfs_device *device = NULL;
 
765
        struct btrfs_chunk *chunk;
 
766
        struct list_head private_devs;
 
767
        struct list_head *dev_list = &info->fs_devices->devices;
 
768
        struct list_head *cur;
 
769
        struct map_lookup *map;
 
770
        int min_stripe_size = 1 * 1024 * 1024;
 
771
        u64 calc_size = 8 * 1024 * 1024;
 
772
        u64 min_free;
 
773
        u64 max_chunk_size = 4 * calc_size;
 
774
        u64 avail = 0;
 
775
        u64 max_avail = 0;
 
776
        u64 percent_max;
 
777
        int num_stripes = 1;
 
778
        int min_stripes = 1;
 
779
        int sub_stripes = 0;
 
780
        int looped = 0;
 
781
        int ret;
 
782
        int index;
 
783
        int stripe_len = BTRFS_STRIPE_LEN;
 
784
        struct btrfs_key key;
 
785
        u64 offset;
 
786
 
 
787
        if (list_empty(dev_list)) {
 
788
                return -ENOSPC;
 
789
        }
 
790
 
 
791
        if (type & (BTRFS_BLOCK_GROUP_RAID0 | BTRFS_BLOCK_GROUP_RAID1 |
 
792
                    BTRFS_BLOCK_GROUP_RAID5 | BTRFS_BLOCK_GROUP_RAID6 |
 
793
                    BTRFS_BLOCK_GROUP_RAID10 |
 
794
                    BTRFS_BLOCK_GROUP_DUP)) {
 
795
                if (type & BTRFS_BLOCK_GROUP_SYSTEM) {
 
796
                        calc_size = 8 * 1024 * 1024;
 
797
                        max_chunk_size = calc_size * 2;
 
798
                        min_stripe_size = 1 * 1024 * 1024;
 
799
                } else if (type & BTRFS_BLOCK_GROUP_DATA) {
 
800
                        calc_size = 1024 * 1024 * 1024;
 
801
                        max_chunk_size = 10 * calc_size;
 
802
                        min_stripe_size = 64 * 1024 * 1024;
 
803
                } else if (type & BTRFS_BLOCK_GROUP_METADATA) {
 
804
                        calc_size = 1024 * 1024 * 1024;
 
805
                        max_chunk_size = 4 * calc_size;
 
806
                        min_stripe_size = 32 * 1024 * 1024;
 
807
                }
 
808
        }
 
809
        if (type & BTRFS_BLOCK_GROUP_RAID1) {
 
810
                num_stripes = min_t(u64, 2,
 
811
                                  btrfs_super_num_devices(info->super_copy));
 
812
                if (num_stripes < 2)
 
813
                        return -ENOSPC;
 
814
                min_stripes = 2;
 
815
        }
 
816
        if (type & BTRFS_BLOCK_GROUP_DUP) {
 
817
                num_stripes = 2;
 
818
                min_stripes = 2;
 
819
        }
 
820
        if (type & (BTRFS_BLOCK_GROUP_RAID0)) {
 
821
                num_stripes = btrfs_super_num_devices(info->super_copy);
 
822
                min_stripes = 2;
 
823
        }
 
824
        if (type & (BTRFS_BLOCK_GROUP_RAID10)) {
 
825
                num_stripes = btrfs_super_num_devices(info->super_copy);
 
826
                if (num_stripes < 4)
 
827
                        return -ENOSPC;
 
828
                num_stripes &= ~(u32)1;
 
829
                sub_stripes = 2;
 
830
                min_stripes = 4;
 
831
        }
 
832
        if (type & (BTRFS_BLOCK_GROUP_RAID5)) {
 
833
                num_stripes = btrfs_super_num_devices(info->super_copy);
 
834
                if (num_stripes < 2)
 
835
                        return -ENOSPC;
 
836
                min_stripes = 2;
 
837
                stripe_len = find_raid56_stripe_len(num_stripes - 1,
 
838
                                    btrfs_super_stripesize(info->super_copy));
 
839
        }
 
840
        if (type & (BTRFS_BLOCK_GROUP_RAID6)) {
 
841
                num_stripes = btrfs_super_num_devices(info->super_copy);
 
842
                if (num_stripes < 3)
 
843
                        return -ENOSPC;
 
844
                min_stripes = 3;
 
845
                stripe_len = find_raid56_stripe_len(num_stripes - 2,
 
846
                                    btrfs_super_stripesize(info->super_copy));
 
847
        }
 
848
 
 
849
        /* we don't want a chunk larger than 10% of the FS */
 
850
        percent_max = div_factor(btrfs_super_total_bytes(info->super_copy), 1);
 
851
        max_chunk_size = min(percent_max, max_chunk_size);
 
852
 
 
853
again:
 
854
        if (chunk_bytes_by_type(type, calc_size, num_stripes, sub_stripes) >
 
855
            max_chunk_size) {
 
856
                calc_size = max_chunk_size;
 
857
                calc_size /= num_stripes;
 
858
                calc_size /= stripe_len;
 
859
                calc_size *= stripe_len;
 
860
        }
 
861
        /* we don't want tiny stripes */
 
862
        calc_size = max_t(u64, calc_size, min_stripe_size);
 
863
 
 
864
        calc_size /= stripe_len;
 
865
        calc_size *= stripe_len;
 
866
        INIT_LIST_HEAD(&private_devs);
 
867
        cur = dev_list->next;
 
868
        index = 0;
 
869
 
 
870
        if (type & BTRFS_BLOCK_GROUP_DUP)
 
871
                min_free = calc_size * 2;
 
872
        else
 
873
                min_free = calc_size;
 
874
 
 
875
        /* build a private list of devices we will allocate from */
 
876
        while(index < num_stripes) {
 
877
                device = list_entry(cur, struct btrfs_device, dev_list);
 
878
                ret = btrfs_device_avail_bytes(trans, device, &avail);
 
879
                if (ret)
 
880
                        return ret;
 
881
                cur = cur->next;
 
882
                if (avail >= min_free) {
 
883
                        list_move_tail(&device->dev_list, &private_devs);
 
884
                        index++;
 
885
                        if (type & BTRFS_BLOCK_GROUP_DUP)
 
886
                                index++;
 
887
                } else if (avail > max_avail)
 
888
                        max_avail = avail;
 
889
                if (cur == dev_list)
 
890
                        break;
 
891
        }
 
892
        if (index < num_stripes) {
 
893
                list_splice(&private_devs, dev_list);
 
894
                if (index >= min_stripes) {
 
895
                        num_stripes = index;
 
896
                        if (type & (BTRFS_BLOCK_GROUP_RAID10)) {
 
897
                                num_stripes /= sub_stripes;
 
898
                                num_stripes *= sub_stripes;
 
899
                        }
 
900
                        looped = 1;
 
901
                        goto again;
 
902
                }
 
903
                if (!looped && max_avail > 0) {
 
904
                        looped = 1;
 
905
                        calc_size = max_avail;
 
906
                        goto again;
 
907
                }
 
908
                return -ENOSPC;
 
909
        }
 
910
        ret = find_next_chunk(chunk_root, BTRFS_FIRST_CHUNK_TREE_OBJECTID,
 
911
                              &offset);
 
912
        if (ret)
 
913
                return ret;
 
914
        key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
 
915
        key.type = BTRFS_CHUNK_ITEM_KEY;
 
916
        key.offset = offset;
 
917
 
 
918
        chunk = kmalloc(btrfs_chunk_item_size(num_stripes), GFP_NOFS);
 
919
        if (!chunk)
 
920
                return -ENOMEM;
 
921
 
 
922
        map = kmalloc(btrfs_map_lookup_size(num_stripes), GFP_NOFS);
 
923
        if (!map) {
 
924
                kfree(chunk);
 
925
                return -ENOMEM;
 
926
        }
 
927
 
 
928
        stripes = &chunk->stripe;
 
929
        *num_bytes = chunk_bytes_by_type(type, calc_size,
 
930
                                         num_stripes, sub_stripes);
 
931
        index = 0;
 
932
        while(index < num_stripes) {
 
933
                struct btrfs_stripe *stripe;
 
934
                BUG_ON(list_empty(&private_devs));
 
935
                cur = private_devs.next;
 
936
                device = list_entry(cur, struct btrfs_device, dev_list);
 
937
 
 
938
                /* loop over this device again if we're doing a dup group */
 
939
                if (!(type & BTRFS_BLOCK_GROUP_DUP) ||
 
940
                    (index == num_stripes - 1))
 
941
                        list_move_tail(&device->dev_list, dev_list);
 
942
 
 
943
                ret = btrfs_alloc_dev_extent(trans, device,
 
944
                             info->chunk_root->root_key.objectid,
 
945
                             BTRFS_FIRST_CHUNK_TREE_OBJECTID, key.offset,
 
946
                             calc_size, &dev_offset);
 
947
                BUG_ON(ret);
 
948
 
 
949
                device->bytes_used += calc_size;
 
950
                ret = btrfs_update_device(trans, device);
 
951
                BUG_ON(ret);
 
952
 
 
953
                map->stripes[index].dev = device;
 
954
                map->stripes[index].physical = dev_offset;
 
955
                stripe = stripes + index;
 
956
                btrfs_set_stack_stripe_devid(stripe, device->devid);
 
957
                btrfs_set_stack_stripe_offset(stripe, dev_offset);
 
958
                memcpy(stripe->dev_uuid, device->uuid, BTRFS_UUID_SIZE);
 
959
                index++;
 
960
        }
 
961
        BUG_ON(!list_empty(&private_devs));
 
962
 
 
963
        /* key was set above */
 
964
        btrfs_set_stack_chunk_length(chunk, *num_bytes);
 
965
        btrfs_set_stack_chunk_owner(chunk, extent_root->root_key.objectid);
 
966
        btrfs_set_stack_chunk_stripe_len(chunk, stripe_len);
 
967
        btrfs_set_stack_chunk_type(chunk, type);
 
968
        btrfs_set_stack_chunk_num_stripes(chunk, num_stripes);
 
969
        btrfs_set_stack_chunk_io_align(chunk, stripe_len);
 
970
        btrfs_set_stack_chunk_io_width(chunk, stripe_len);
 
971
        btrfs_set_stack_chunk_sector_size(chunk, extent_root->sectorsize);
 
972
        btrfs_set_stack_chunk_sub_stripes(chunk, sub_stripes);
 
973
        map->sector_size = extent_root->sectorsize;
 
974
        map->stripe_len = stripe_len;
 
975
        map->io_align = stripe_len;
 
976
        map->io_width = stripe_len;
 
977
        map->type = type;
 
978
        map->num_stripes = num_stripes;
 
979
        map->sub_stripes = sub_stripes;
 
980
 
 
981
        ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
 
982
                                btrfs_chunk_item_size(num_stripes));
 
983
        BUG_ON(ret);
 
984
        *start = key.offset;;
 
985
 
 
986
        map->ce.start = key.offset;
 
987
        map->ce.size = *num_bytes;
 
988
 
 
989
        ret = insert_cache_extent(&info->mapping_tree.cache_tree, &map->ce);
 
990
        BUG_ON(ret);
 
991
 
 
992
        if (type & BTRFS_BLOCK_GROUP_SYSTEM) {
 
993
                ret = btrfs_add_system_chunk(trans, chunk_root, &key,
 
994
                                    chunk, btrfs_chunk_item_size(num_stripes));
 
995
                BUG_ON(ret);
 
996
        }
 
997
 
 
998
        kfree(chunk);
 
999
        return ret;
 
1000
}
 
1001
 
 
1002
int btrfs_alloc_data_chunk(struct btrfs_trans_handle *trans,
 
1003
                           struct btrfs_root *extent_root, u64 *start,
 
1004
                           u64 num_bytes, u64 type)
 
1005
{
 
1006
        u64 dev_offset;
 
1007
        struct btrfs_fs_info *info = extent_root->fs_info;
 
1008
        struct btrfs_root *chunk_root = info->chunk_root;
 
1009
        struct btrfs_stripe *stripes;
 
1010
        struct btrfs_device *device = NULL;
 
1011
        struct btrfs_chunk *chunk;
 
1012
        struct list_head *dev_list = &info->fs_devices->devices;
 
1013
        struct list_head *cur;
 
1014
        struct map_lookup *map;
 
1015
        u64 calc_size = 8 * 1024 * 1024;
 
1016
        int num_stripes = 1;
 
1017
        int sub_stripes = 0;
 
1018
        int ret;
 
1019
        int index;
 
1020
        int stripe_len = BTRFS_STRIPE_LEN;
 
1021
        struct btrfs_key key;
 
1022
 
 
1023
        key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
 
1024
        key.type = BTRFS_CHUNK_ITEM_KEY;
 
1025
        ret = find_next_chunk(chunk_root, BTRFS_FIRST_CHUNK_TREE_OBJECTID,
 
1026
                              &key.offset);
 
1027
        if (ret)
 
1028
                return ret;
 
1029
 
 
1030
        chunk = kmalloc(btrfs_chunk_item_size(num_stripes), GFP_NOFS);
 
1031
        if (!chunk)
 
1032
                return -ENOMEM;
 
1033
 
 
1034
        map = kmalloc(btrfs_map_lookup_size(num_stripes), GFP_NOFS);
 
1035
        if (!map) {
 
1036
                kfree(chunk);
 
1037
                return -ENOMEM;
 
1038
        }
 
1039
 
 
1040
        stripes = &chunk->stripe;
 
1041
        calc_size = num_bytes;
 
1042
 
 
1043
        index = 0;
 
1044
        cur = dev_list->next;
 
1045
        device = list_entry(cur, struct btrfs_device, dev_list);
 
1046
 
 
1047
        while (index < num_stripes) {
 
1048
                struct btrfs_stripe *stripe;
 
1049
 
 
1050
                ret = btrfs_alloc_dev_extent(trans, device,
 
1051
                             info->chunk_root->root_key.objectid,
 
1052
                             BTRFS_FIRST_CHUNK_TREE_OBJECTID, key.offset,
 
1053
                             calc_size, &dev_offset);
 
1054
                BUG_ON(ret);
 
1055
 
 
1056
                device->bytes_used += calc_size;
 
1057
                ret = btrfs_update_device(trans, device);
 
1058
                BUG_ON(ret);
 
1059
 
 
1060
                map->stripes[index].dev = device;
 
1061
                map->stripes[index].physical = dev_offset;
 
1062
                stripe = stripes + index;
 
1063
                btrfs_set_stack_stripe_devid(stripe, device->devid);
 
1064
                btrfs_set_stack_stripe_offset(stripe, dev_offset);
 
1065
                memcpy(stripe->dev_uuid, device->uuid, BTRFS_UUID_SIZE);
 
1066
                index++;
 
1067
        }
 
1068
 
 
1069
        /* key was set above */
 
1070
        btrfs_set_stack_chunk_length(chunk, num_bytes);
 
1071
        btrfs_set_stack_chunk_owner(chunk, extent_root->root_key.objectid);
 
1072
        btrfs_set_stack_chunk_stripe_len(chunk, stripe_len);
 
1073
        btrfs_set_stack_chunk_type(chunk, type);
 
1074
        btrfs_set_stack_chunk_num_stripes(chunk, num_stripes);
 
1075
        btrfs_set_stack_chunk_io_align(chunk, stripe_len);
 
1076
        btrfs_set_stack_chunk_io_width(chunk, stripe_len);
 
1077
        btrfs_set_stack_chunk_sector_size(chunk, extent_root->sectorsize);
 
1078
        btrfs_set_stack_chunk_sub_stripes(chunk, sub_stripes);
 
1079
        map->sector_size = extent_root->sectorsize;
 
1080
        map->stripe_len = stripe_len;
 
1081
        map->io_align = stripe_len;
 
1082
        map->io_width = stripe_len;
 
1083
        map->type = type;
 
1084
        map->num_stripes = num_stripes;
 
1085
        map->sub_stripes = sub_stripes;
 
1086
 
 
1087
        ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
 
1088
                                btrfs_chunk_item_size(num_stripes));
 
1089
        BUG_ON(ret);
 
1090
        *start = key.offset;
 
1091
 
 
1092
        map->ce.start = key.offset;
 
1093
        map->ce.size = num_bytes;
 
1094
 
 
1095
        ret = insert_cache_extent(&info->mapping_tree.cache_tree, &map->ce);
 
1096
        BUG_ON(ret);
 
1097
 
 
1098
        kfree(chunk);
 
1099
        return ret;
 
1100
}
 
1101
 
 
1102
int btrfs_num_copies(struct btrfs_mapping_tree *map_tree, u64 logical, u64 len)
 
1103
{
 
1104
        struct cache_extent *ce;
 
1105
        struct map_lookup *map;
 
1106
        int ret;
 
1107
 
 
1108
        ce = search_cache_extent(&map_tree->cache_tree, logical);
 
1109
        BUG_ON(!ce);
 
1110
        BUG_ON(ce->start > logical || ce->start + ce->size < logical);
 
1111
        map = container_of(ce, struct map_lookup, ce);
 
1112
 
 
1113
        if (map->type & (BTRFS_BLOCK_GROUP_DUP | BTRFS_BLOCK_GROUP_RAID1))
 
1114
                ret = map->num_stripes;
 
1115
        else if (map->type & BTRFS_BLOCK_GROUP_RAID10)
 
1116
                ret = map->sub_stripes;
 
1117
        else if (map->type & BTRFS_BLOCK_GROUP_RAID5)
 
1118
                ret = 2;
 
1119
        else if (map->type & BTRFS_BLOCK_GROUP_RAID6)
 
1120
                ret = 3;
 
1121
        else
 
1122
                ret = 1;
 
1123
        return ret;
 
1124
}
 
1125
 
 
1126
int btrfs_next_metadata(struct btrfs_mapping_tree *map_tree, u64 *logical,
 
1127
                        u64 *size)
 
1128
{
 
1129
        struct cache_extent *ce;
 
1130
        struct map_lookup *map;
 
1131
 
 
1132
        ce = search_cache_extent(&map_tree->cache_tree, *logical);
 
1133
 
 
1134
        while (ce) {
 
1135
                ce = next_cache_extent(ce);
 
1136
                if (!ce)
 
1137
                        return -ENOENT;
 
1138
 
 
1139
                map = container_of(ce, struct map_lookup, ce);
 
1140
                if (map->type & BTRFS_BLOCK_GROUP_METADATA) {
 
1141
                        *logical = ce->start;
 
1142
                        *size = ce->size;
 
1143
                        return 0;
 
1144
                }
 
1145
        }
 
1146
 
 
1147
        return -ENOENT;
 
1148
}
 
1149
 
 
1150
int btrfs_rmap_block(struct btrfs_mapping_tree *map_tree,
 
1151
                     u64 chunk_start, u64 physical, u64 devid,
 
1152
                     u64 **logical, int *naddrs, int *stripe_len)
 
1153
{
 
1154
        struct cache_extent *ce;
 
1155
        struct map_lookup *map;
 
1156
        u64 *buf;
 
1157
        u64 bytenr;
 
1158
        u64 length;
 
1159
        u64 stripe_nr;
 
1160
        u64 rmap_len;
 
1161
        int i, j, nr = 0;
 
1162
 
 
1163
        ce = search_cache_extent(&map_tree->cache_tree, chunk_start);
 
1164
        BUG_ON(!ce);
 
1165
        map = container_of(ce, struct map_lookup, ce);
 
1166
 
 
1167
        length = ce->size;
 
1168
        rmap_len = map->stripe_len;
 
1169
        if (map->type & BTRFS_BLOCK_GROUP_RAID10)
 
1170
                length = ce->size / (map->num_stripes / map->sub_stripes);
 
1171
        else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
 
1172
                length = ce->size / map->num_stripes;
 
1173
        else if (map->type & (BTRFS_BLOCK_GROUP_RAID5 |
 
1174
                              BTRFS_BLOCK_GROUP_RAID6)) {
 
1175
                length = ce->size / nr_data_stripes(map);
 
1176
                rmap_len = map->stripe_len * nr_data_stripes(map);
 
1177
        }
 
1178
 
 
1179
        buf = kzalloc(sizeof(u64) * map->num_stripes, GFP_NOFS);
 
1180
 
 
1181
        for (i = 0; i < map->num_stripes; i++) {
 
1182
                if (devid && map->stripes[i].dev->devid != devid)
 
1183
                        continue;
 
1184
                if (map->stripes[i].physical > physical ||
 
1185
                    map->stripes[i].physical + length <= physical)
 
1186
                        continue;
 
1187
 
 
1188
                stripe_nr = (physical - map->stripes[i].physical) /
 
1189
                            map->stripe_len;
 
1190
 
 
1191
                if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
 
1192
                        stripe_nr = (stripe_nr * map->num_stripes + i) /
 
1193
                                    map->sub_stripes;
 
1194
                } else if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
 
1195
                        stripe_nr = stripe_nr * map->num_stripes + i;
 
1196
                } /* else if RAID[56], multiply by nr_data_stripes().
 
1197
                   * Alternatively, just use rmap_len below instead of
 
1198
                   * map->stripe_len */
 
1199
 
 
1200
                bytenr = ce->start + stripe_nr * rmap_len;
 
1201
                for (j = 0; j < nr; j++) {
 
1202
                        if (buf[j] == bytenr)
 
1203
                                break;
 
1204
                }
 
1205
                if (j == nr)
 
1206
                        buf[nr++] = bytenr;
 
1207
        }
 
1208
 
 
1209
        *logical = buf;
 
1210
        *naddrs = nr;
 
1211
        *stripe_len = rmap_len;
 
1212
 
 
1213
        return 0;
 
1214
}
 
1215
 
 
1216
static inline int parity_smaller(u64 a, u64 b)
 
1217
{
 
1218
        return a > b;
 
1219
}
 
1220
 
 
1221
/* Bubble-sort the stripe set to put the parity/syndrome stripes last */
 
1222
static void sort_parity_stripes(struct btrfs_multi_bio *bbio, u64 *raid_map)
 
1223
{
 
1224
        struct btrfs_bio_stripe s;
 
1225
        int i;
 
1226
        u64 l;
 
1227
        int again = 1;
 
1228
 
 
1229
        while (again) {
 
1230
                again = 0;
 
1231
                for (i = 0; i < bbio->num_stripes - 1; i++) {
 
1232
                        if (parity_smaller(raid_map[i], raid_map[i+1])) {
 
1233
                                s = bbio->stripes[i];
 
1234
                                l = raid_map[i];
 
1235
                                bbio->stripes[i] = bbio->stripes[i+1];
 
1236
                                raid_map[i] = raid_map[i+1];
 
1237
                                bbio->stripes[i+1] = s;
 
1238
                                raid_map[i+1] = l;
 
1239
                                again = 1;
 
1240
                        }
 
1241
                }
 
1242
        }
 
1243
}
 
1244
 
 
1245
int btrfs_map_block(struct btrfs_mapping_tree *map_tree, int rw,
 
1246
                    u64 logical, u64 *length,
 
1247
                    struct btrfs_multi_bio **multi_ret, int mirror_num,
 
1248
                    u64 **raid_map_ret)
 
1249
{
 
1250
        return __btrfs_map_block(map_tree, rw, logical, length, NULL,
 
1251
                                 multi_ret, mirror_num, raid_map_ret);
 
1252
}
 
1253
 
 
1254
int __btrfs_map_block(struct btrfs_mapping_tree *map_tree, int rw,
 
1255
                    u64 logical, u64 *length, u64 *type,
 
1256
                    struct btrfs_multi_bio **multi_ret, int mirror_num,
 
1257
                    u64 **raid_map_ret)
 
1258
{
 
1259
        struct cache_extent *ce;
 
1260
        struct map_lookup *map;
 
1261
        u64 offset;
 
1262
        u64 stripe_offset;
 
1263
        u64 stripe_nr;
 
1264
        u64 *raid_map = NULL;
 
1265
        int stripes_allocated = 8;
 
1266
        int stripes_required = 1;
 
1267
        int stripe_index;
 
1268
        int i;
 
1269
        struct btrfs_multi_bio *multi = NULL;
 
1270
 
 
1271
        if (multi_ret && rw == READ) {
 
1272
                stripes_allocated = 1;
 
1273
        }
 
1274
again:
 
1275
        ce = search_cache_extent(&map_tree->cache_tree, logical);
 
1276
        if (!ce) {
 
1277
                kfree(multi);
 
1278
                return -ENOENT;
 
1279
        }
 
1280
        if (ce->start > logical || ce->start + ce->size < logical) {
 
1281
                kfree(multi);
 
1282
                return -ENOENT;
 
1283
        }
 
1284
 
 
1285
        if (multi_ret) {
 
1286
                multi = kzalloc(btrfs_multi_bio_size(stripes_allocated),
 
1287
                                GFP_NOFS);
 
1288
                if (!multi)
 
1289
                        return -ENOMEM;
 
1290
        }
 
1291
        map = container_of(ce, struct map_lookup, ce);
 
1292
        offset = logical - ce->start;
 
1293
 
 
1294
        if (rw == WRITE) {
 
1295
                if (map->type & (BTRFS_BLOCK_GROUP_RAID1 |
 
1296
                                 BTRFS_BLOCK_GROUP_DUP)) {
 
1297
                        stripes_required = map->num_stripes;
 
1298
                } else if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
 
1299
                        stripes_required = map->sub_stripes;
 
1300
                }
 
1301
        }
 
1302
        if (map->type & (BTRFS_BLOCK_GROUP_RAID5 | BTRFS_BLOCK_GROUP_RAID6)
 
1303
            && multi_ret && ((rw & WRITE) || mirror_num > 1) && raid_map_ret) {
 
1304
                    /* RAID[56] write or recovery. Return all stripes */
 
1305
                    stripes_required = map->num_stripes;
 
1306
 
 
1307
                    /* Only allocate the map if we've already got a large enough multi_ret */
 
1308
                    if (stripes_allocated >= stripes_required) {
 
1309
                            raid_map = kmalloc(sizeof(u64) * map->num_stripes, GFP_NOFS);
 
1310
                            if (!raid_map) {
 
1311
                                    kfree(multi);
 
1312
                                    return -ENOMEM;
 
1313
                            }
 
1314
                    }
 
1315
        }
 
1316
 
 
1317
        /* if our multi bio struct is too small, back off and try again */
 
1318
        if (multi_ret && stripes_allocated < stripes_required) {
 
1319
                stripes_allocated = stripes_required;
 
1320
                kfree(multi);
 
1321
                multi = NULL;
 
1322
                goto again;
 
1323
        }
 
1324
        stripe_nr = offset;
 
1325
        /*
 
1326
         * stripe_nr counts the total number of stripes we have to stride
 
1327
         * to get to this block
 
1328
         */
 
1329
        stripe_nr = stripe_nr / map->stripe_len;
 
1330
 
 
1331
        stripe_offset = stripe_nr * map->stripe_len;
 
1332
        BUG_ON(offset < stripe_offset);
 
1333
 
 
1334
        /* stripe_offset is the offset of this block in its stripe*/
 
1335
        stripe_offset = offset - stripe_offset;
 
1336
 
 
1337
        if (map->type & (BTRFS_BLOCK_GROUP_RAID0 | BTRFS_BLOCK_GROUP_RAID1 |
 
1338
                         BTRFS_BLOCK_GROUP_RAID5 | BTRFS_BLOCK_GROUP_RAID6 |
 
1339
                         BTRFS_BLOCK_GROUP_RAID10 |
 
1340
                         BTRFS_BLOCK_GROUP_DUP)) {
 
1341
                /* we limit the length of each bio to what fits in a stripe */
 
1342
                *length = min_t(u64, ce->size - offset,
 
1343
                              map->stripe_len - stripe_offset);
 
1344
        } else {
 
1345
                *length = ce->size - offset;
 
1346
        }
 
1347
 
 
1348
        if (!multi_ret)
 
1349
                goto out;
 
1350
 
 
1351
        multi->num_stripes = 1;
 
1352
        stripe_index = 0;
 
1353
        if (map->type & BTRFS_BLOCK_GROUP_RAID1) {
 
1354
                if (rw == WRITE)
 
1355
                        multi->num_stripes = map->num_stripes;
 
1356
                else if (mirror_num)
 
1357
                        stripe_index = mirror_num - 1;
 
1358
                else
 
1359
                        stripe_index = stripe_nr % map->num_stripes;
 
1360
        } else if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
 
1361
                int factor = map->num_stripes / map->sub_stripes;
 
1362
 
 
1363
                stripe_index = stripe_nr % factor;
 
1364
                stripe_index *= map->sub_stripes;
 
1365
 
 
1366
                if (rw == WRITE)
 
1367
                        multi->num_stripes = map->sub_stripes;
 
1368
                else if (mirror_num)
 
1369
                        stripe_index += mirror_num - 1;
 
1370
 
 
1371
                stripe_nr = stripe_nr / factor;
 
1372
        } else if (map->type & BTRFS_BLOCK_GROUP_DUP) {
 
1373
                if (rw == WRITE)
 
1374
                        multi->num_stripes = map->num_stripes;
 
1375
                else if (mirror_num)
 
1376
                        stripe_index = mirror_num - 1;
 
1377
        } else if (map->type & (BTRFS_BLOCK_GROUP_RAID5 |
 
1378
                                BTRFS_BLOCK_GROUP_RAID6)) {
 
1379
 
 
1380
                if (raid_map) {
 
1381
                        int rot;
 
1382
                        u64 tmp;
 
1383
                        u64 raid56_full_stripe_start;
 
1384
                        u64 full_stripe_len = nr_data_stripes(map) * map->stripe_len;
 
1385
 
 
1386
                        /*
 
1387
                         * align the start of our data stripe in the logical
 
1388
                         * address space
 
1389
                         */
 
1390
                        raid56_full_stripe_start = offset / full_stripe_len;
 
1391
                        raid56_full_stripe_start *= full_stripe_len;
 
1392
 
 
1393
                        /* get the data stripe number */
 
1394
                        stripe_nr = raid56_full_stripe_start / map->stripe_len;
 
1395
                        stripe_nr = stripe_nr / nr_data_stripes(map);
 
1396
 
 
1397
                        /* Work out the disk rotation on this stripe-set */
 
1398
                        rot = stripe_nr % map->num_stripes;
 
1399
 
 
1400
                        /* Fill in the logical address of each stripe */
 
1401
                        tmp = stripe_nr * nr_data_stripes(map);
 
1402
 
 
1403
                        for (i = 0; i < nr_data_stripes(map); i++)
 
1404
                                raid_map[(i+rot) % map->num_stripes] =
 
1405
                                        ce->start + (tmp + i) * map->stripe_len;
 
1406
 
 
1407
                        raid_map[(i+rot) % map->num_stripes] = BTRFS_RAID5_P_STRIPE;
 
1408
                        if (map->type & BTRFS_BLOCK_GROUP_RAID6)
 
1409
                                raid_map[(i+rot+1) % map->num_stripes] = BTRFS_RAID6_Q_STRIPE;
 
1410
 
 
1411
                        *length = map->stripe_len;
 
1412
                        stripe_index = 0;
 
1413
                        stripe_offset = 0;
 
1414
                        multi->num_stripes = map->num_stripes;
 
1415
                } else {
 
1416
                        stripe_index = stripe_nr % nr_data_stripes(map);
 
1417
                        stripe_nr = stripe_nr / nr_data_stripes(map);
 
1418
 
 
1419
                        /*
 
1420
                         * Mirror #0 or #1 means the original data block.
 
1421
                         * Mirror #2 is RAID5 parity block.
 
1422
                         * Mirror #3 is RAID6 Q block.
 
1423
                         */
 
1424
                        if (mirror_num > 1)
 
1425
                                stripe_index = nr_data_stripes(map) + mirror_num - 2;
 
1426
 
 
1427
                        /* We distribute the parity blocks across stripes */
 
1428
                        stripe_index = (stripe_nr + stripe_index) % map->num_stripes;
 
1429
                }
 
1430
        } else {
 
1431
                /*
 
1432
                 * after this do_div call, stripe_nr is the number of stripes
 
1433
                 * on this device we have to walk to find the data, and
 
1434
                 * stripe_index is the number of our device in the stripe array
 
1435
                 */
 
1436
                stripe_index = stripe_nr % map->num_stripes;
 
1437
                stripe_nr = stripe_nr / map->num_stripes;
 
1438
        }
 
1439
        BUG_ON(stripe_index >= map->num_stripes);
 
1440
 
 
1441
        for (i = 0; i < multi->num_stripes; i++) {
 
1442
                multi->stripes[i].physical =
 
1443
                        map->stripes[stripe_index].physical + stripe_offset +
 
1444
                        stripe_nr * map->stripe_len;
 
1445
                multi->stripes[i].dev = map->stripes[stripe_index].dev;
 
1446
                stripe_index++;
 
1447
        }
 
1448
        *multi_ret = multi;
 
1449
 
 
1450
        if (type)
 
1451
                *type = map->type;
 
1452
 
 
1453
        if (raid_map) {
 
1454
                sort_parity_stripes(multi, raid_map);
 
1455
                *raid_map_ret = raid_map;
 
1456
        }
 
1457
out:
 
1458
        return 0;
 
1459
}
 
1460
 
 
1461
struct btrfs_device *btrfs_find_device(struct btrfs_root *root, u64 devid,
 
1462
                                       u8 *uuid, u8 *fsid)
 
1463
{
 
1464
        struct btrfs_device *device;
 
1465
        struct btrfs_fs_devices *cur_devices;
 
1466
 
 
1467
        cur_devices = root->fs_info->fs_devices;
 
1468
        while (cur_devices) {
 
1469
                if (!fsid ||
 
1470
                    !memcmp(cur_devices->fsid, fsid, BTRFS_UUID_SIZE)) {
 
1471
                        device = __find_device(&cur_devices->devices,
 
1472
                                               devid, uuid);
 
1473
                        if (device)
 
1474
                                return device;
 
1475
                }
 
1476
                cur_devices = cur_devices->seed;
 
1477
        }
 
1478
        return NULL;
 
1479
}
 
1480
 
 
1481
struct btrfs_device *
 
1482
btrfs_find_device_by_devid(struct btrfs_fs_devices *fs_devices,
 
1483
                           u64 devid, int instance)
 
1484
{
 
1485
        struct list_head *head = &fs_devices->devices;
 
1486
        struct btrfs_device *dev;
 
1487
        int num_found = 0;
 
1488
 
 
1489
        list_for_each_entry(dev, head, dev_list) {
 
1490
                if (dev->devid == devid && num_found++ == instance)
 
1491
                        return dev;
 
1492
        }
 
1493
        return NULL;
 
1494
}
 
1495
 
 
1496
int btrfs_chunk_readonly(struct btrfs_root *root, u64 chunk_offset)
 
1497
{
 
1498
        struct cache_extent *ce;
 
1499
        struct map_lookup *map;
 
1500
        struct btrfs_mapping_tree *map_tree = &root->fs_info->mapping_tree;
 
1501
        int readonly = 0;
 
1502
        int i;
 
1503
 
 
1504
        /*
 
1505
         * During chunk recovering, we may fail to find block group's
 
1506
         * corresponding chunk, we will rebuild it later
 
1507
         */
 
1508
        ce = search_cache_extent(&map_tree->cache_tree, chunk_offset);
 
1509
        if (!root->fs_info->is_chunk_recover)
 
1510
                BUG_ON(!ce);
 
1511
        else
 
1512
                return 0;
 
1513
 
 
1514
        map = container_of(ce, struct map_lookup, ce);
 
1515
        for (i = 0; i < map->num_stripes; i++) {
 
1516
                if (!map->stripes[i].dev->writeable) {
 
1517
                        readonly = 1;
 
1518
                        break;
 
1519
                }
 
1520
        }
 
1521
 
 
1522
        return readonly;
 
1523
}
 
1524
 
 
1525
static struct btrfs_device *fill_missing_device(u64 devid)
 
1526
{
 
1527
        struct btrfs_device *device;
 
1528
 
 
1529
        device = kzalloc(sizeof(*device), GFP_NOFS);
 
1530
        device->devid = devid;
 
1531
        device->fd = -1;
 
1532
        return device;
 
1533
}
 
1534
 
 
1535
static int read_one_chunk(struct btrfs_root *root, struct btrfs_key *key,
 
1536
                          struct extent_buffer *leaf,
 
1537
                          struct btrfs_chunk *chunk)
 
1538
{
 
1539
        struct btrfs_mapping_tree *map_tree = &root->fs_info->mapping_tree;
 
1540
        struct map_lookup *map;
 
1541
        struct cache_extent *ce;
 
1542
        u64 logical;
 
1543
        u64 length;
 
1544
        u64 devid;
 
1545
        u8 uuid[BTRFS_UUID_SIZE];
 
1546
        int num_stripes;
 
1547
        int ret;
 
1548
        int i;
 
1549
 
 
1550
        logical = key->offset;
 
1551
        length = btrfs_chunk_length(leaf, chunk);
 
1552
 
 
1553
        ce = search_cache_extent(&map_tree->cache_tree, logical);
 
1554
 
 
1555
        /* already mapped? */
 
1556
        if (ce && ce->start <= logical && ce->start + ce->size > logical) {
 
1557
                return 0;
 
1558
        }
 
1559
 
 
1560
        num_stripes = btrfs_chunk_num_stripes(leaf, chunk);
 
1561
        map = kmalloc(btrfs_map_lookup_size(num_stripes), GFP_NOFS);
 
1562
        if (!map)
 
1563
                return -ENOMEM;
 
1564
 
 
1565
        map->ce.start = logical;
 
1566
        map->ce.size = length;
 
1567
        map->num_stripes = num_stripes;
 
1568
        map->io_width = btrfs_chunk_io_width(leaf, chunk);
 
1569
        map->io_align = btrfs_chunk_io_align(leaf, chunk);
 
1570
        map->sector_size = btrfs_chunk_sector_size(leaf, chunk);
 
1571
        map->stripe_len = btrfs_chunk_stripe_len(leaf, chunk);
 
1572
        map->type = btrfs_chunk_type(leaf, chunk);
 
1573
        map->sub_stripes = btrfs_chunk_sub_stripes(leaf, chunk);
 
1574
 
 
1575
        for (i = 0; i < num_stripes; i++) {
 
1576
                map->stripes[i].physical =
 
1577
                        btrfs_stripe_offset_nr(leaf, chunk, i);
 
1578
                devid = btrfs_stripe_devid_nr(leaf, chunk, i);
 
1579
                read_extent_buffer(leaf, uuid, (unsigned long)
 
1580
                                   btrfs_stripe_dev_uuid_nr(chunk, i),
 
1581
                                   BTRFS_UUID_SIZE);
 
1582
                map->stripes[i].dev = btrfs_find_device(root, devid, uuid,
 
1583
                                                        NULL);
 
1584
                if (!map->stripes[i].dev) {
 
1585
                        map->stripes[i].dev = fill_missing_device(devid);
 
1586
                        printf("warning, device %llu is missing\n",
 
1587
                               (unsigned long long)devid);
 
1588
                }
 
1589
 
 
1590
        }
 
1591
        ret = insert_cache_extent(&map_tree->cache_tree, &map->ce);
 
1592
        BUG_ON(ret);
 
1593
 
 
1594
        return 0;
 
1595
}
 
1596
 
 
1597
static int fill_device_from_item(struct extent_buffer *leaf,
 
1598
                                 struct btrfs_dev_item *dev_item,
 
1599
                                 struct btrfs_device *device)
 
1600
{
 
1601
        unsigned long ptr;
 
1602
 
 
1603
        device->devid = btrfs_device_id(leaf, dev_item);
 
1604
        device->total_bytes = btrfs_device_total_bytes(leaf, dev_item);
 
1605
        device->bytes_used = btrfs_device_bytes_used(leaf, dev_item);
 
1606
        device->type = btrfs_device_type(leaf, dev_item);
 
1607
        device->io_align = btrfs_device_io_align(leaf, dev_item);
 
1608
        device->io_width = btrfs_device_io_width(leaf, dev_item);
 
1609
        device->sector_size = btrfs_device_sector_size(leaf, dev_item);
 
1610
 
 
1611
        ptr = (unsigned long)btrfs_device_uuid(dev_item);
 
1612
        read_extent_buffer(leaf, device->uuid, ptr, BTRFS_UUID_SIZE);
 
1613
 
 
1614
        return 0;
 
1615
}
 
1616
 
 
1617
static int open_seed_devices(struct btrfs_root *root, u8 *fsid)
 
1618
{
 
1619
        struct btrfs_fs_devices *fs_devices;
 
1620
        int ret;
 
1621
 
 
1622
        fs_devices = root->fs_info->fs_devices->seed;
 
1623
        while (fs_devices) {
 
1624
                if (!memcmp(fs_devices->fsid, fsid, BTRFS_UUID_SIZE)) {
 
1625
                        ret = 0;
 
1626
                        goto out;
 
1627
                }
 
1628
                fs_devices = fs_devices->seed;
 
1629
        }
 
1630
 
 
1631
        fs_devices = find_fsid(fsid);
 
1632
        if (!fs_devices) {
 
1633
                ret = -ENOENT;
 
1634
                goto out;
 
1635
        }
 
1636
 
 
1637
        ret = btrfs_open_devices(fs_devices, O_RDONLY);
 
1638
        if (ret)
 
1639
                goto out;
 
1640
 
 
1641
        fs_devices->seed = root->fs_info->fs_devices->seed;
 
1642
        root->fs_info->fs_devices->seed = fs_devices;
 
1643
out:
 
1644
        return ret;
 
1645
}
 
1646
 
 
1647
static int read_one_dev(struct btrfs_root *root,
 
1648
                        struct extent_buffer *leaf,
 
1649
                        struct btrfs_dev_item *dev_item)
 
1650
{
 
1651
        struct btrfs_device *device;
 
1652
        u64 devid;
 
1653
        int ret = 0;
 
1654
        u8 fs_uuid[BTRFS_UUID_SIZE];
 
1655
        u8 dev_uuid[BTRFS_UUID_SIZE];
 
1656
 
 
1657
        devid = btrfs_device_id(leaf, dev_item);
 
1658
        read_extent_buffer(leaf, dev_uuid,
 
1659
                           (unsigned long)btrfs_device_uuid(dev_item),
 
1660
                           BTRFS_UUID_SIZE);
 
1661
        read_extent_buffer(leaf, fs_uuid,
 
1662
                           (unsigned long)btrfs_device_fsid(dev_item),
 
1663
                           BTRFS_UUID_SIZE);
 
1664
 
 
1665
        if (memcmp(fs_uuid, root->fs_info->fsid, BTRFS_UUID_SIZE)) {
 
1666
                ret = open_seed_devices(root, fs_uuid);
 
1667
                if (ret)
 
1668
                        return ret;
 
1669
        }
 
1670
 
 
1671
        device = btrfs_find_device(root, devid, dev_uuid, fs_uuid);
 
1672
        if (!device) {
 
1673
                printk("warning devid %llu not found already\n",
 
1674
                        (unsigned long long)devid);
 
1675
                device = kzalloc(sizeof(*device), GFP_NOFS);
 
1676
                if (!device)
 
1677
                        return -ENOMEM;
 
1678
                device->fd = -1;
 
1679
                list_add(&device->dev_list,
 
1680
                         &root->fs_info->fs_devices->devices);
 
1681
        }
 
1682
 
 
1683
        fill_device_from_item(leaf, dev_item, device);
 
1684
        device->dev_root = root->fs_info->dev_root;
 
1685
        return ret;
 
1686
}
 
1687
 
 
1688
int btrfs_read_sys_array(struct btrfs_root *root)
 
1689
{
 
1690
        struct btrfs_super_block *super_copy = root->fs_info->super_copy;
 
1691
        struct extent_buffer *sb;
 
1692
        struct btrfs_disk_key *disk_key;
 
1693
        struct btrfs_chunk *chunk;
 
1694
        struct btrfs_key key;
 
1695
        u32 num_stripes;
 
1696
        u32 len = 0;
 
1697
        u8 *ptr;
 
1698
        u8 *array_end;
 
1699
        int ret = 0;
 
1700
 
 
1701
        sb = btrfs_find_create_tree_block(root, BTRFS_SUPER_INFO_OFFSET,
 
1702
                                          BTRFS_SUPER_INFO_SIZE);
 
1703
        if (!sb)
 
1704
                return -ENOMEM;
 
1705
        btrfs_set_buffer_uptodate(sb);
 
1706
        write_extent_buffer(sb, super_copy, 0, sizeof(*super_copy));
 
1707
        array_end = ((u8 *)super_copy->sys_chunk_array) +
 
1708
                    btrfs_super_sys_array_size(super_copy);
 
1709
 
 
1710
        /*
 
1711
         * we do this loop twice, once for the device items and
 
1712
         * once for all of the chunks.  This way there are device
 
1713
         * structs filled in for every chunk
 
1714
         */
 
1715
        ptr = super_copy->sys_chunk_array;
 
1716
 
 
1717
        while (ptr < array_end) {
 
1718
                disk_key = (struct btrfs_disk_key *)ptr;
 
1719
                btrfs_disk_key_to_cpu(&key, disk_key);
 
1720
 
 
1721
                len = sizeof(*disk_key);
 
1722
                ptr += len;
 
1723
 
 
1724
                if (key.type == BTRFS_CHUNK_ITEM_KEY) {
 
1725
                        chunk = (struct btrfs_chunk *)(ptr - (u8 *)super_copy);
 
1726
                        ret = read_one_chunk(root, &key, sb, chunk);
 
1727
                        if (ret)
 
1728
                                break;
 
1729
                        num_stripes = btrfs_chunk_num_stripes(sb, chunk);
 
1730
                        len = btrfs_chunk_item_size(num_stripes);
 
1731
                } else {
 
1732
                        BUG();
 
1733
                }
 
1734
                ptr += len;
 
1735
        }
 
1736
        free_extent_buffer(sb);
 
1737
        return ret;
 
1738
}
 
1739
 
 
1740
int btrfs_read_chunk_tree(struct btrfs_root *root)
 
1741
{
 
1742
        struct btrfs_path *path;
 
1743
        struct extent_buffer *leaf;
 
1744
        struct btrfs_key key;
 
1745
        struct btrfs_key found_key;
 
1746
        int ret;
 
1747
        int slot;
 
1748
 
 
1749
        root = root->fs_info->chunk_root;
 
1750
 
 
1751
        path = btrfs_alloc_path();
 
1752
        if (!path)
 
1753
                return -ENOMEM;
 
1754
 
 
1755
        /*
 
1756
         * Read all device items, and then all the chunk items. All
 
1757
         * device items are found before any chunk item (their object id
 
1758
         * is smaller than the lowest possible object id for a chunk
 
1759
         * item - BTRFS_FIRST_CHUNK_TREE_OBJECTID).
 
1760
         */
 
1761
        key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 
1762
        key.offset = 0;
 
1763
        key.type = 0;
 
1764
        ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 
1765
        if (ret < 0)
 
1766
                goto error;
 
1767
        while(1) {
 
1768
                leaf = path->nodes[0];
 
1769
                slot = path->slots[0];
 
1770
                if (slot >= btrfs_header_nritems(leaf)) {
 
1771
                        ret = btrfs_next_leaf(root, path);
 
1772
                        if (ret == 0)
 
1773
                                continue;
 
1774
                        if (ret < 0)
 
1775
                                goto error;
 
1776
                        break;
 
1777
                }
 
1778
                btrfs_item_key_to_cpu(leaf, &found_key, slot);
 
1779
                if (found_key.type == BTRFS_DEV_ITEM_KEY) {
 
1780
                        struct btrfs_dev_item *dev_item;
 
1781
                        dev_item = btrfs_item_ptr(leaf, slot,
 
1782
                                                  struct btrfs_dev_item);
 
1783
                        ret = read_one_dev(root, leaf, dev_item);
 
1784
                        BUG_ON(ret);
 
1785
                } else if (found_key.type == BTRFS_CHUNK_ITEM_KEY) {
 
1786
                        struct btrfs_chunk *chunk;
 
1787
                        chunk = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
 
1788
                        ret = read_one_chunk(root, &found_key, leaf, chunk);
 
1789
                        BUG_ON(ret);
 
1790
                }
 
1791
                path->slots[0]++;
 
1792
        }
 
1793
 
 
1794
        ret = 0;
 
1795
error:
 
1796
        btrfs_free_path(path);
 
1797
        return ret;
 
1798
}
 
1799
 
 
1800
struct list_head *btrfs_scanned_uuids(void)
 
1801
{
 
1802
        return &fs_uuids;
 
1803
}
 
1804
 
 
1805
static int rmw_eb(struct btrfs_fs_info *info,
 
1806
                  struct extent_buffer *eb, struct extent_buffer *orig_eb)
 
1807
{
 
1808
        int ret;
 
1809
        unsigned long orig_off = 0;
 
1810
        unsigned long dest_off = 0;
 
1811
        unsigned long copy_len = eb->len;
 
1812
 
 
1813
        ret = read_whole_eb(info, eb, 0);
 
1814
        if (ret)
 
1815
                return ret;
 
1816
 
 
1817
        if (eb->start + eb->len <= orig_eb->start ||
 
1818
            eb->start >= orig_eb->start + orig_eb->len)
 
1819
                return 0;
 
1820
        /*
 
1821
         * | ----- orig_eb ------- |
 
1822
         *         | ----- stripe -------  |
 
1823
         *         | ----- orig_eb ------- |
 
1824
         *              | ----- orig_eb ------- |
 
1825
         */
 
1826
        if (eb->start > orig_eb->start)
 
1827
                orig_off = eb->start - orig_eb->start;
 
1828
        if (orig_eb->start > eb->start)
 
1829
                dest_off = orig_eb->start - eb->start;
 
1830
 
 
1831
        if (copy_len > orig_eb->len - orig_off)
 
1832
                copy_len = orig_eb->len - orig_off;
 
1833
        if (copy_len > eb->len - dest_off)
 
1834
                copy_len = eb->len - dest_off;
 
1835
 
 
1836
        memcpy(eb->data + dest_off, orig_eb->data + orig_off, copy_len);
 
1837
        return 0;
 
1838
}
 
1839
 
 
1840
static void split_eb_for_raid56(struct btrfs_fs_info *info,
 
1841
                                struct extent_buffer *orig_eb,
 
1842
                               struct extent_buffer **ebs,
 
1843
                               u64 stripe_len, u64 *raid_map,
 
1844
                               int num_stripes)
 
1845
{
 
1846
        struct extent_buffer *eb;
 
1847
        u64 start = orig_eb->start;
 
1848
        u64 this_eb_start;
 
1849
        int i;
 
1850
        int ret;
 
1851
 
 
1852
        for (i = 0; i < num_stripes; i++) {
 
1853
                if (raid_map[i] >= BTRFS_RAID5_P_STRIPE)
 
1854
                        break;
 
1855
 
 
1856
                eb = malloc(sizeof(struct extent_buffer) + stripe_len);
 
1857
                if (!eb)
 
1858
                        BUG();
 
1859
                memset(eb, 0, sizeof(struct extent_buffer) + stripe_len);
 
1860
 
 
1861
                eb->start = raid_map[i];
 
1862
                eb->len = stripe_len;
 
1863
                eb->refs = 1;
 
1864
                eb->flags = 0;
 
1865
                eb->fd = -1;
 
1866
                eb->dev_bytenr = (u64)-1;
 
1867
 
 
1868
                this_eb_start = raid_map[i];
 
1869
 
 
1870
                if (start > this_eb_start ||
 
1871
                    start + orig_eb->len < this_eb_start + stripe_len) {
 
1872
                        ret = rmw_eb(info, eb, orig_eb);
 
1873
                        BUG_ON(ret);
 
1874
                } else {
 
1875
                        memcpy(eb->data, orig_eb->data + eb->start - start, stripe_len);
 
1876
                }
 
1877
                ebs[i] = eb;
 
1878
        }
 
1879
}
 
1880
 
 
1881
int write_raid56_with_parity(struct btrfs_fs_info *info,
 
1882
                             struct extent_buffer *eb,
 
1883
                             struct btrfs_multi_bio *multi,
 
1884
                             u64 stripe_len, u64 *raid_map)
 
1885
{
 
1886
        struct extent_buffer **ebs, *p_eb = NULL, *q_eb = NULL;
 
1887
        int i;
 
1888
        int j;
 
1889
        int ret;
 
1890
        int alloc_size = eb->len;
 
1891
 
 
1892
        ebs = kmalloc(sizeof(*ebs) * multi->num_stripes, GFP_NOFS);
 
1893
        BUG_ON(!ebs);
 
1894
 
 
1895
        if (stripe_len > alloc_size)
 
1896
                alloc_size = stripe_len;
 
1897
 
 
1898
        split_eb_for_raid56(info, eb, ebs, stripe_len, raid_map,
 
1899
                            multi->num_stripes);
 
1900
 
 
1901
        for (i = 0; i < multi->num_stripes; i++) {
 
1902
                struct extent_buffer *new_eb;
 
1903
                if (raid_map[i] < BTRFS_RAID5_P_STRIPE) {
 
1904
                        ebs[i]->dev_bytenr = multi->stripes[i].physical;
 
1905
                        ebs[i]->fd = multi->stripes[i].dev->fd;
 
1906
                        multi->stripes[i].dev->total_ios++;
 
1907
                        BUG_ON(ebs[i]->start != raid_map[i]);
 
1908
                        continue;
 
1909
                }
 
1910
                new_eb = kmalloc(sizeof(*eb) + alloc_size, GFP_NOFS);
 
1911
                BUG_ON(!new_eb);
 
1912
                new_eb->dev_bytenr = multi->stripes[i].physical;
 
1913
                new_eb->fd = multi->stripes[i].dev->fd;
 
1914
                multi->stripes[i].dev->total_ios++;
 
1915
                new_eb->len = stripe_len;
 
1916
 
 
1917
                if (raid_map[i] == BTRFS_RAID5_P_STRIPE)
 
1918
                        p_eb = new_eb;
 
1919
                else if (raid_map[i] == BTRFS_RAID6_Q_STRIPE)
 
1920
                        q_eb = new_eb;
 
1921
        }
 
1922
        if (q_eb) {
 
1923
                void **pointers;
 
1924
 
 
1925
                pointers = kmalloc(sizeof(*pointers) * multi->num_stripes,
 
1926
                                   GFP_NOFS);
 
1927
                BUG_ON(!pointers);
 
1928
 
 
1929
                ebs[multi->num_stripes - 2] = p_eb;
 
1930
                ebs[multi->num_stripes - 1] = q_eb;
 
1931
 
 
1932
                for (i = 0; i < multi->num_stripes; i++)
 
1933
                        pointers[i] = ebs[i]->data;
 
1934
 
 
1935
                raid6_gen_syndrome(multi->num_stripes, stripe_len, pointers);
 
1936
                kfree(pointers);
 
1937
        } else {
 
1938
                ebs[multi->num_stripes - 1] = p_eb;
 
1939
                memcpy(p_eb->data, ebs[0]->data, stripe_len);
 
1940
                for (j = 1; j < multi->num_stripes - 1; j++) {
 
1941
                        for (i = 0; i < stripe_len; i += sizeof(unsigned long)) {
 
1942
                                *(unsigned long *)(p_eb->data + i) ^=
 
1943
                                        *(unsigned long *)(ebs[j]->data + i);
 
1944
                        }
 
1945
                }
 
1946
        }
 
1947
 
 
1948
        for (i = 0; i < multi->num_stripes; i++) {
 
1949
                ret = write_extent_to_disk(ebs[i]);
 
1950
                BUG_ON(ret);
 
1951
                if (ebs[i] != eb)
 
1952
                        kfree(ebs[i]);
 
1953
        }
 
1954
 
 
1955
        kfree(ebs);
 
1956
 
 
1957
        return 0;
 
1958
}