SandboXP

1
// -------------------------------------------------
2
// ----------------- FILESYSTEM---------------------
3
// -------------------------------------------------
4
// Implementation of a unix filesystem in memory.
5

6
"use strict";
7

8
var S_IRWXUGO = 0x1FF;
9
var S_IFMT = 0xF000;
10
var S_IFSOCK = 0xC000;
11
var S_IFLNK = 0xA000;
12
var S_IFREG = 0x8000;
13
var S_IFBLK = 0x6000;
14
var S_IFDIR = 0x4000;
15
var S_IFCHR = 0x2000;
16

17
//var S_IFIFO  0010000
18
//var S_ISUID  0004000
19
//var S_ISGID  0002000
20
//var S_ISVTX  0001000
21

22
var O_RDONLY = 0x0000; // open for reading only
23
var O_WRONLY = 0x0001; // open for writing only
24
var O_RDWR = 0x0002; // open for reading and writing
25
var O_ACCMODE = 0x0003; // mask for above modes
26

27
var STATUS_INVALID = -0x1;
28
var STATUS_OK = 0x0;
29
var STATUS_ON_STORAGE = 0x2;
30
var STATUS_UNLINKED = 0x4;
31
var STATUS_FORWARDING = 0x5;
32

33

34
/** @const */ var JSONFS_VERSION = 3;
35

36

37
/** @const */ var JSONFS_IDX_NAME = 0;
38
/** @const */ var JSONFS_IDX_SIZE = 1;
39
/** @const */ var JSONFS_IDX_MTIME = 2;
40
/** @const */ var JSONFS_IDX_MODE = 3;
41
/** @const */ var JSONFS_IDX_UID = 4;
42
/** @const */ var JSONFS_IDX_GID = 5;
43
/** @const */ var JSONFS_IDX_TARGET = 6;
44
/** @const */ var JSONFS_IDX_SHA256 = 6;
45

46

47
/**
48
 * @constructor
49
 * @param {!FileStorageInterface} storage
50
 * @param {{ last_qidnumber: number }=} qidcounter Another fs's qidcounter to synchronise with.
51
 */
52
function FS(storage, qidcounter) {
53
    /** @type {Array.<!Inode>} */
54
    this.inodes = [];
55
    this.events = [];
56

57
    this.storage = storage;
58

59
    this.qidcounter = qidcounter || { last_qidnumber: 0 };
60

61
    //this.tar = new TAR(this);
62

63
    this.inodedata = {};
64

65
    this.total_size = 256 * 1024 * 1024 * 1024;
66
    this.used_size = 0;
67

68
    /** @type {!Array<!FSMountInfo>} */
69
    this.mounts = [];
70

71
    //RegisterMessage("LoadFilesystem", this.LoadFilesystem.bind(this) );
72
    //RegisterMessage("MergeFile", this.MergeFile.bind(this) );
73
    //RegisterMessage("tar",
74
    //    function(data) {
75
    //        SendToMaster("tar", this.tar.Pack(data));
76
    //    }.bind(this)
77
    //);
78
    //RegisterMessage("sync",
79
    //    function(data) {
80
    //        SendToMaster("sync", this.tar.Pack(data));
81
    //    }.bind(this)
82
    //);
83

84
    // root entry
85
    this.CreateDirectory("", -1);
86
}
87

88
FS.prototype.get_state = function()
89
{
90
    let state = [];
91

92
    state[0] = this.inodes;
93
    state[1] = this.qidcounter.last_qidnumber;
94
    state[2] = [];
95
    for(const [id, data] of Object.entries(this.inodedata))
96
    {
97
        if((this.inodes[id].mode & S_IFDIR) === 0)
98
        {
99
            state[2].push([id, data]);
100
        }
101
    }
102
    state[3] = this.total_size;
103
    state[4] = this.used_size;
104
    state = state.concat(this.mounts);
105

106
    return state;
107
};
108

109
FS.prototype.set_state = function(state)
110
{
111
    this.inodes = state[0].map(state => { const inode = new Inode(0); inode.set_state(state); return inode; });
112
    this.qidcounter.last_qidnumber = state[1];
113
    this.inodedata = {};
114
    for(let [key, value] of state[2])
115
    {
116
        if(value.buffer.byteLength !== value.byteLength)
117
        {
118
            // make a copy if we didn't get one
119
            value = value.slice();
120
        }
121

122
        this.inodedata[key] = value;
123
    }
124
    this.total_size = state[3];
125
    this.used_size = state[4];
126
    this.mounts = state.slice(5);
127
};
128

129

130
// -----------------------------------------------------
131

132
FS.prototype.AddEvent = function(id, OnEvent) {
133
    var inode = this.inodes[id];
134
    if (inode.status == STATUS_OK || inode.status == STATUS_ON_STORAGE) {
135
        OnEvent();
136
    }
137
    else if(this.is_forwarder(inode))
138
    {
139
        this.follow_fs(inode).AddEvent(inode.foreign_id, OnEvent);
140
    }
141
    else
142
    {
143
        this.events.push({id: id, OnEvent: OnEvent});
144
    }
145
};
146

147
FS.prototype.HandleEvent = function(id) {
148
    const inode = this.inodes[id];
149
    if(this.is_forwarder(inode))
150
    {
151
        this.follow_fs(inode).HandleEvent(inode.foreign_id);
152
    }
153
    //message.Debug("number of events: " + this.events.length);
154
    var newevents = [];
155
    for(var i=0; i<this.events.length; i++) {
156
        if (this.events[i].id == id) {
157
            this.events[i].OnEvent();
158
        } else {
159
            newevents.push(this.events[i]);
160
        }
161
    }
162
    this.events = newevents;
163
};
164

165
FS.prototype.load_from_json = function(fs, done)
166
{
167
    dbg_assert(fs, "Invalid fs passed to load_from_json");
168

169
    if(fs["version"] !== JSONFS_VERSION)
170
    {
171
        throw "The filesystem JSON format has changed. " +
172
              "Please update your fs2json (https://github.com/copy/fs2json) and recreate the filesystem JSON.";
173
    }
174

175
    var fsroot = fs["fsroot"];
176
    this.used_size = fs["size"];
177

178
    for(var i = 0; i < fsroot.length; i++) {
179
        this.LoadRecursive(fsroot[i], 0);
180
    }
181

182
    //if(DEBUG)
183
    //{
184
    //    this.Check();
185
    //}
186

187
    done && done();
188
};
189

190
FS.prototype.LoadRecursive = function(data, parentid)
191
{
192
    var inode = this.CreateInode();
193

194
    const name = data[JSONFS_IDX_NAME];
195
    inode.size = data[JSONFS_IDX_SIZE];
196
    inode.mtime = data[JSONFS_IDX_MTIME];
197
    inode.ctime = inode.mtime;
198
    inode.atime = inode.mtime;
199
    inode.mode = data[JSONFS_IDX_MODE];
200
    inode.uid = data[JSONFS_IDX_UID];
201
    inode.gid = data[JSONFS_IDX_GID];
202

203
    var ifmt = inode.mode & S_IFMT;
204

205
    if(ifmt === S_IFDIR)
206
    {
207
        this.PushInode(inode, parentid, name);
208
        this.LoadDir(this.inodes.length - 1, data[JSONFS_IDX_TARGET]);
209
    }
210
    else if(ifmt === S_IFREG)
211
    {
212
        inode.status = STATUS_ON_STORAGE;
213
        inode.sha256sum = data[JSONFS_IDX_SHA256];
214
        dbg_assert(inode.sha256sum);
215
        this.PushInode(inode, parentid, name);
216
    }
217
    else if(ifmt === S_IFLNK)
218
    {
219
        inode.symlink = data[JSONFS_IDX_TARGET];
220
        this.PushInode(inode, parentid, name);
221
    }
222
    else if(ifmt === S_IFSOCK)
223
    {
224
        // socket: ignore
225
    }
226
    else
227
    {
228
        dbg_log("Unexpected ifmt: " + h(ifmt) + " (" + name + ")");
229
    }
230
};
231

232
FS.prototype.LoadDir = function(parentid, children)
233
{
234
    for(var i = 0; i < children.length; i++) {
235
        this.LoadRecursive(children[i], parentid);
236
    }
237
};
238

239

240
// -----------------------------------------------------
241

242
/**
243
 * @private
244
 * @param {Inode} inode
245
 * @return {boolean}
246
 */
247
FS.prototype.should_be_linked = function(inode)
248
{
249
    // Note: Non-root forwarder inode could still have a non-forwarder parent, so don't use
250
    // parent inode to check.
251
    return !this.is_forwarder(inode) || inode.foreign_id === 0;
252
};
253

254
/**
255
 * @private
256
 * @param {number} parentid
257
 * @param {number} idx
258
 * @param {string} name
259
 */
260
FS.prototype.link_under_dir = function(parentid, idx, name)
261
{
262
    const inode = this.inodes[idx];
263
    const parent_inode = this.inodes[parentid];
264

265
    dbg_assert(!this.is_forwarder(parent_inode),
266
        "Filesystem: Shouldn't link under fowarder parents");
267
    dbg_assert(this.IsDirectory(parentid),
268
        "Filesystem: Can't link under non-directories");
269
    dbg_assert(this.should_be_linked(inode),
270
        "Filesystem: Can't link across filesystems apart from their root");
271
    dbg_assert(inode.nlinks >= 0,
272
        "Filesystem: Found negative nlinks value of " + inode.nlinks);
273
    dbg_assert(!parent_inode.direntries.has(name),
274
        "Filesystem: Name '" + name + "' is already taken");
275

276
    parent_inode.direntries.set(name, idx);
277
    inode.nlinks++;
278

279
    if(this.IsDirectory(idx))
280
    {
281
        dbg_assert(!inode.direntries.has(".."),
282
            "Filesystem: Cannot link a directory twice");
283

284
        if(!inode.direntries.has(".")) inode.nlinks++;
285
        inode.direntries.set(".", idx);
286

287
        inode.direntries.set("..", parentid);
288
        parent_inode.nlinks++;
289
    }
290
};
291

292
/**
293
 * @private
294
 * @param {number} parentid
295
 * @param {string} name
296
 */
297
FS.prototype.unlink_from_dir = function(parentid, name)
298
{
299
    const idx = this.Search(parentid, name);
300
    const inode = this.inodes[idx];
301
    const parent_inode = this.inodes[parentid];
302

303
    dbg_assert(!this.is_forwarder(parent_inode), "Filesystem: Can't unlink from forwarders");
304
    dbg_assert(this.IsDirectory(parentid), "Filesystem: Can't unlink from non-directories");
305

306
    const exists = parent_inode.direntries.delete(name);
307
    if(!exists)
308
    {
309
        dbg_assert(false, "Filesystem: Can't unlink non-existent file: " + name);
310
        return;
311
    }
312

313
    inode.nlinks--;
314

315
    if(this.IsDirectory(idx))
316
    {
317
        dbg_assert(inode.direntries.get("..") === parentid,
318
            "Filesystem: Found directory with bad parent id");
319

320
        inode.direntries.delete("..");
321
        parent_inode.nlinks--;
322
    }
323

324
    dbg_assert(inode.nlinks >= 0,
325
        "Filesystem: Found negative nlinks value of " + inode.nlinks);
326
};
327

328
FS.prototype.PushInode = function(inode, parentid, name) {
329
    if (parentid != -1) {
330
        this.inodes.push(inode);
331
        inode.fid = this.inodes.length - 1;
332
        this.link_under_dir(parentid, inode.fid, name);
333
        return;
334
    } else {
335
        if (this.inodes.length == 0) { // if root directory
336
            this.inodes.push(inode);
337
            inode.direntries.set(".", 0);
338
            inode.direntries.set("..", 0);
339
            inode.nlinks = 2;
340
            return;
341
        }
342
    }
343

344
    message.Debug("Error in Filesystem: Pushed inode with name = "+ name + " has no parent");
345
    message.Abort();
346

347
};
348

349
/** @constructor */
350
function Inode(qidnumber)
351
{
352
    this.direntries = new Map(); // maps filename to inode id
353
    this.status = 0;
354
    this.size = 0x0;
355
    this.uid = 0x0;
356
    this.gid = 0x0;
357
    this.fid = 0;
358
    this.ctime = 0;
359
    this.atime = 0;
360
    this.mtime = 0;
361
    this.major = 0x0;
362
    this.minor = 0x0;
363
    this.symlink = "";
364
    this.mode = 0x01ED;
365
    this.qid = {
366
        type: 0,
367
        version: 0,
368
        path: qidnumber,
369
    };
370
    this.caps = undefined;
371
    this.nlinks = 0;
372
    this.sha256sum = "";
373

374
    /** @type{!Array<!FSLockRegion>} */
375
    this.locks = []; // lock regions applied to the file, sorted by starting offset.
376

377
    // For forwarders:
378
    this.mount_id = -1; // which fs in this.mounts does this inode forward to?
379
    this.foreign_id = -1; // which foreign inode id does it represent?
380

381
    //this.qid_type = 0;
382
    //this.qid_version = 0;
383
    //this.qid_path = qidnumber;
384
}
385

386
Inode.prototype.get_state = function()
387
{
388
    const state = [];
389
    state[0] = this.mode;
390

391
    if((this.mode & S_IFMT) === S_IFDIR)
392
    {
393
        state[1] = [...this.direntries];
394
    }
395
    else if((this.mode & S_IFMT) === S_IFREG)
396
    {
397
        state[1] = this.sha256sum;
398
    }
399
    else if((this.mode & S_IFMT) === S_IFLNK)
400
    {
401
        state[1] = this.symlink;
402
    }
403
    else if((this.mode & S_IFMT) === S_IFSOCK)
404
    {
405
        state[1] = [this.minor, this.major];
406
    }
407
    else
408
    {
409
        state[1] = null;
410
    }
411

412
    state[2] = this.locks;
413
    state[3] = this.status;
414
    state[4] = this.size;
415
    state[5] = this.uid;
416
    state[6] = this.gid;
417
    state[7] = this.fid;
418
    state[8] = this.ctime;
419
    state[9] = this.atime;
420
    state[10] = this.mtime;
421
    state[11] = this.qid.version;
422
    state[12] = this.qid.path;
423
    state[13] = this.nlinks;
424

425
    //state[23] = this.mount_id;
426
    //state[24] = this.foreign_id;
427
    //state[25] = this.caps; // currently not writable
428
    return state;
429
};
430

431
Inode.prototype.set_state = function(state)
432
{
433
    this.mode = state[0];
434

435
    if((this.mode & S_IFMT) === S_IFDIR)
436
    {
437
        this.direntries = new Map();
438
        for(const [name, entry] of state[1])
439
        {
440
            this.direntries.set(name, entry);
441
        }
442
    }
443
    else if((this.mode & S_IFMT) === S_IFREG)
444
    {
445
        this.sha256sum = state[1];
446
    }
447
    else if((this.mode & S_IFMT) === S_IFLNK)
448
    {
449
        this.symlink = state[1];
450
    }
451
    else if((this.mode & S_IFMT) === S_IFSOCK)
452
    {
453
        [this.minor, this.major] = state[1];
454
    }
455
    else
456
    {
457
        // Nothing
458
    }
459

460
    this.locks = [];
461
    for(const lock_state of state[2])
462
    {
463
        const lock = new FSLockRegion();
464
        lock.set_state(lock_state);
465
        this.locks.push(lock);
466
    }
467
    this.status = state[3];
468
    this.size = state[4];
469
    this.uid = state[5];
470
    this.gid = state[6];
471
    this.fid = state[7];
472
    this.ctime = state[8];
473
    this.atime = state[9];
474
    this.mtime = state[10];
475
    this.qid.type = (this.mode & S_IFMT) >> 8;
476
    this.qid.version = state[11];
477
    this.qid.path = state[12];
478
    this.nlinks = state[13];
479

480
    //this.mount_id = state[23];
481
    //this.foreign_id = state[24];
482
    //this.caps = state[20];
483
};
484

485
/**
486
 * Clones given inode to new idx, effectively diverting the inode to new idx value.
487
 * Hence, original idx value is now free to use without losing the original information.
488
 * @private
489
 * @param {number} parentid Parent of target to divert.
490
 * @param {string} filename Name of target to divert.
491
 * @return {number} New idx of diversion.
492
 */
493
FS.prototype.divert = function(parentid, filename)
494
{
495
    const old_idx = this.Search(parentid, filename);
496
    const old_inode = this.inodes[old_idx];
497
    const new_inode = new Inode(-1);
498

499
    dbg_assert(old_inode, "Filesystem divert: name (" + filename + ") not found");
500
    dbg_assert(this.IsDirectory(old_idx) || old_inode.nlinks <= 1,
501
        "Filesystem: can't divert hardlinked file '" + filename + "' with nlinks=" +
502
        old_inode.nlinks);
503

504
    // Shallow copy is alright.
505
    Object.assign(new_inode, old_inode);
506

507
    const idx = this.inodes.length;
508
    this.inodes.push(new_inode);
509
    new_inode.fid = idx;
510

511
    // Relink references
512
    if(this.is_forwarder(old_inode))
513
    {
514
        this.mounts[old_inode.mount_id].backtrack.set(old_inode.foreign_id, idx);
515
    }
516
    if(this.should_be_linked(old_inode))
517
    {
518
        this.unlink_from_dir(parentid, filename);
519
        this.link_under_dir(parentid, idx, filename);
520
    }
521

522
    // Update children
523
    if(this.IsDirectory(old_idx) && !this.is_forwarder(old_inode))
524
    {
525
        for(const [name, child_id] of new_inode.direntries)
526
        {
527
            if(name === "." || name === "..") continue;
528
            if(this.IsDirectory(child_id))
529
            {
530
                this.inodes[child_id].direntries.set("..", idx);
531
            }
532
        }
533
    }
534

535
    // Relocate local data if any.
536
    this.inodedata[idx] = this.inodedata[old_idx];
537
    delete this.inodedata[old_idx];
538

539
    // Retire old reference information.
540
    old_inode.direntries = new Map();
541
    old_inode.nlinks = 0;
542

543
    return idx;
544
};
545

546
/**
547
 * Copy all non-redundant info.
548
 * References left untouched: local idx value and links
549
 * @private
550
 * @param {!Inode} src_inode
551
 * @param {!Inode} dest_inode
552
 */
553
FS.prototype.copy_inode = function(src_inode, dest_inode)
554
{
555
    Object.assign(dest_inode, src_inode, {
556
        fid: dest_inode.fid,
557
        direntries: dest_inode.direntries,
558
        nlinks: dest_inode.nlinks,
559
    });
560
};
561

562
FS.prototype.CreateInode = function() {
563
    //console.log("CreateInode", Error().stack);
564
    const now = Math.round(Date.now() / 1000);
565
    const inode = new Inode(++this.qidcounter.last_qidnumber);
566
    inode.atime = inode.ctime = inode.mtime = now;
567
    return inode;
568
};
569

570

571
// Note: parentid = -1 for initial root directory.
572
FS.prototype.CreateDirectory = function(name, parentid) {
573
    const parent_inode = this.inodes[parentid];
574
    if(parentid >= 0 && this.is_forwarder(parent_inode))
575
    {
576
        const foreign_parentid = parent_inode.foreign_id;
577
        const foreign_id = this.follow_fs(parent_inode).CreateDirectory(name, foreign_parentid);
578
        return this.create_forwarder(parent_inode.mount_id, foreign_id);
579
    }
580
    var x = this.CreateInode();
581
    x.mode = 0x01FF | S_IFDIR;
582
    if (parentid >= 0) {
583
        x.uid = this.inodes[parentid].uid;
584
        x.gid = this.inodes[parentid].gid;
585
        x.mode = (this.inodes[parentid].mode & 0x1FF) | S_IFDIR;
586
    }
587
    x.qid.type = S_IFDIR >> 8;
588
    this.PushInode(x, parentid, name);
589
    this.NotifyListeners(this.inodes.length-1, 'newdir');
590
    return this.inodes.length-1;
591
};
592

593
FS.prototype.CreateFile = function(filename, parentid) {
594
    const parent_inode = this.inodes[parentid];
595
    if(this.is_forwarder(parent_inode))
596
    {
597
        const foreign_parentid = parent_inode.foreign_id;
598
        const foreign_id = this.follow_fs(parent_inode).CreateFile(filename, foreign_parentid);
599
        return this.create_forwarder(parent_inode.mount_id, foreign_id);
600
    }
601
    var x = this.CreateInode();
602
    x.uid = this.inodes[parentid].uid;
603
    x.gid = this.inodes[parentid].gid;
604
    x.qid.type = S_IFREG >> 8;
605
    x.mode = (this.inodes[parentid].mode & 0x1B6) | S_IFREG;
606
    this.PushInode(x, parentid, filename);
607
    this.NotifyListeners(this.inodes.length-1, 'newfile');
608
    return this.inodes.length-1;
609
};
610

611

612
FS.prototype.CreateNode = function(filename, parentid, major, minor) {
613
    const parent_inode = this.inodes[parentid];
614
    if(this.is_forwarder(parent_inode))
615
    {
616
        const foreign_parentid = parent_inode.foreign_id;
617
        const foreign_id =
618
            this.follow_fs(parent_inode).CreateNode(filename, foreign_parentid, major, minor);
619
        return this.create_forwarder(parent_inode.mount_id, foreign_id);
620
    }
621
    var x = this.CreateInode();
622
    x.major = major;
623
    x.minor = minor;
624
    x.uid = this.inodes[parentid].uid;
625
    x.gid = this.inodes[parentid].gid;
626
    x.qid.type = S_IFSOCK >> 8;
627
    x.mode = (this.inodes[parentid].mode & 0x1B6);
628
    this.PushInode(x, parentid, filename);
629
    return this.inodes.length-1;
630
};
631

632
FS.prototype.CreateSymlink = function(filename, parentid, symlink) {
633
    const parent_inode = this.inodes[parentid];
634
    if(this.is_forwarder(parent_inode))
635
    {
636
        const foreign_parentid = parent_inode.foreign_id;
637
        const foreign_id =
638
            this.follow_fs(parent_inode).CreateSymlink(filename, foreign_parentid, symlink);
639
        return this.create_forwarder(parent_inode.mount_id, foreign_id);
640
    }
641
    var x = this.CreateInode();
642
    x.uid = this.inodes[parentid].uid;
643
    x.gid = this.inodes[parentid].gid;
644
    x.qid.type = S_IFLNK >> 8;
645
    x.symlink = symlink;
646
    x.mode = S_IFLNK;
647
    this.PushInode(x, parentid, filename);
648
    return this.inodes.length-1;
649
};
650

651
FS.prototype.CreateTextFile = async function(filename, parentid, str) {
652
    const parent_inode = this.inodes[parentid];
653
    if(this.is_forwarder(parent_inode))
654
    {
655
        const foreign_parentid = parent_inode.foreign_id;
656
        const foreign_id = await
657
            this.follow_fs(parent_inode).CreateTextFile(filename, foreign_parentid, str);
658
        return this.create_forwarder(parent_inode.mount_id, foreign_id);
659
    }
660
    var id = this.CreateFile(filename, parentid);
661
    var x = this.inodes[id];
662
    var data = new Uint8Array(str.length);
663
    x.size = str.length;
664
    for (var j = 0; j < str.length; j++) {
665
        data[j] = str.charCodeAt(j);
666
    }
667
    await this.set_data(id, data);
668
    return id;
669
};
670

671
/**
672
 * @param {Uint8Array} buffer
673
 */
674
FS.prototype.CreateBinaryFile = async function(filename, parentid, buffer) {
675
    const parent_inode = this.inodes[parentid];
676
    if(this.is_forwarder(parent_inode))
677
    {
678
        const foreign_parentid = parent_inode.foreign_id;
679
        const foreign_id = await
680
            this.follow_fs(parent_inode).CreateBinaryFile(filename, foreign_parentid, buffer);
681
        return this.create_forwarder(parent_inode.mount_id, foreign_id);
682
    }
683
    var id = this.CreateFile(filename, parentid);
684
    var x = this.inodes[id];
685
    var data = new Uint8Array(buffer.length);
686
    data.set(buffer);
687
    await this.set_data(id, data);
688
    x.size = buffer.length;
689
    return id;
690
};
691

692

693
FS.prototype.OpenInode = function(id, mode) {
694
    var inode = this.inodes[id];
695
    if(this.is_forwarder(inode))
696
    {
697
        return this.follow_fs(inode).OpenInode(inode.foreign_id, mode);
698
    }
699
    if ((inode.mode&S_IFMT) == S_IFDIR) {
700
        this.FillDirectory(id);
701
    }
702
    /*
703
    var type = "";
704
    switch(inode.mode&S_IFMT) {
705
        case S_IFREG: type = "File"; break;
706
        case S_IFBLK: type = "Block Device"; break;
707
        case S_IFDIR: type = "Directory"; break;
708
        case S_IFCHR: type = "Character Device"; break;
709
    }
710
    */
711
    //message.Debug("open:" + this.GetFullPath(id) +  " type: " + inode.mode + " status:" + inode.status);
712
    return true;
713
};
714

715
FS.prototype.CloseInode = async function(id) {
716
    //message.Debug("close: " + this.GetFullPath(id));
717
    var inode = this.inodes[id];
718
    if(this.is_forwarder(inode))
719
    {
720
        return await this.follow_fs(inode).CloseInode(inode.foreign_id);
721
    }
722
    if(inode.status === STATUS_ON_STORAGE)
723
    {
724
        this.storage.uncache(inode.sha256sum);
725
    }
726
    if (inode.status == STATUS_UNLINKED) {
727
        //message.Debug("Filesystem: Delete unlinked file");
728
        inode.status = STATUS_INVALID;
729
        await this.DeleteData(id);
730
    }
731
};
732

733
/**
734
 * @return {!Promise<number>} 0 if success, or -errno if failured.
735
 */
736
FS.prototype.Rename = async function(olddirid, oldname, newdirid, newname) {
737
    // message.Debug("Rename " + oldname + " to " + newname);
738
    if ((olddirid == newdirid) && (oldname == newname)) {
739
        return 0;
740
    }
741
    var oldid = this.Search(olddirid, oldname);
742
    if(oldid === -1)
743
    {
744
        return -ENOENT;
745
    }
746

747
    // For event notification near end of method.
748
    var oldpath = this.GetFullPath(olddirid) + "/" + oldname;
749

750
    var newid = this.Search(newdirid, newname);
751
    if (newid != -1) {
752
        const ret = this.Unlink(newdirid, newname);
753
        if(ret < 0) return ret;
754
    }
755

756
    var idx = oldid; // idx contains the id which we want to rename
757
    var inode = this.inodes[idx];
758
    const olddir = this.inodes[olddirid];
759
    const newdir = this.inodes[newdirid];
760

761
    if(!this.is_forwarder(olddir) && !this.is_forwarder(newdir))
762
    {
763
        // Move inode within current filesystem.
764

765
        this.unlink_from_dir(olddirid, oldname);
766
        this.link_under_dir(newdirid, idx, newname);
767

768
        inode.qid.version++;
769
    }
770
    else if(this.is_forwarder(olddir) && olddir.mount_id === newdir.mount_id)
771
    {
772
        // Move inode within the same child filesystem.
773

774
        const ret = await
775
            this.follow_fs(olddir).Rename(olddir.foreign_id, oldname, newdir.foreign_id, newname);
776

777
        if(ret < 0) return ret;
778
    }
779
    else if(this.is_a_root(idx))
780
    {
781
        // The actual inode is a root of some descendant filesystem.
782
        // Moving mountpoint across fs not supported - needs to update all corresponding forwarders.
783
        dbg_log("XXX: Attempted to move mountpoint (" + oldname + ") - skipped", LOG_9P);
784
        return -EPERM;
785
    }
786
    else if(!this.IsDirectory(idx) && this.GetInode(idx).nlinks > 1)
787
    {
788
        // Move hardlinked inode vertically in mount tree.
789
        dbg_log("XXX: Attempted to move hardlinked file (" + oldname + ") " +
790
                "across filesystems - skipped", LOG_9P);
791
        return -EPERM;
792
    }
793
    else
794
    {
795
        // Jump between filesystems.
796

797
        // Can't work with both old and new inode information without first diverting the old
798
        // information into a new idx value.
799
        const diverted_old_idx = this.divert(olddirid, oldname);
800
        const old_real_inode = this.GetInode(idx);
801

802
        const data = await this.Read(diverted_old_idx, 0, old_real_inode.size);
803

804
        if(this.is_forwarder(newdir))
805
        {
806
            // Create new inode.
807
            const foreign_fs = this.follow_fs(newdir);
808
            const foreign_id = this.IsDirectory(diverted_old_idx) ?
809
                foreign_fs.CreateDirectory(newname, newdir.foreign_id) :
810
                foreign_fs.CreateFile(newname, newdir.foreign_id);
811

812
            const new_real_inode = foreign_fs.GetInode(foreign_id);
813
            this.copy_inode(old_real_inode, new_real_inode);
814

815
            // Point to this new location.
816
            this.set_forwarder(idx, newdir.mount_id, foreign_id);
817
        }
818
        else
819
        {
820
            // Replace current forwarder with real inode.
821
            this.delete_forwarder(inode);
822
            this.copy_inode(old_real_inode, inode);
823

824
            // Link into new location in this filesystem.
825
            this.link_under_dir(newdirid, idx, newname);
826
        }
827

828
        // Rewrite data to newly created destination.
829
        await this.ChangeSize(idx, old_real_inode.size);
830
        if(data && data.length)
831
        {
832
            await this.Write(idx, 0, data.length, data);
833
        }
834

835
        // Move children to newly created destination.
836
        if(this.IsDirectory(idx))
837
        {
838
            for(const child_filename of this.GetChildren(diverted_old_idx))
839
            {
840
                const ret = await this.Rename(diverted_old_idx, child_filename, idx, child_filename);
841
                if(ret < 0) return ret;
842
            }
843
        }
844

845
        // Perform destructive changes only after migration succeeded.
846
        await this.DeleteData(diverted_old_idx);
847
        const ret = this.Unlink(olddirid, oldname);
848
        if(ret < 0) return ret;
849
    }
850

851
    this.NotifyListeners(idx, "rename", {oldpath: oldpath});
852

853
    return 0;
854
};
855

856
FS.prototype.Write = async function(id, offset, count, buffer) {
857
    this.NotifyListeners(id, 'write');
858
    var inode = this.inodes[id];
859

860
    if(this.is_forwarder(inode))
861
    {
862
        const foreign_id = inode.foreign_id;
863
        await this.follow_fs(inode).Write(foreign_id, offset, count, buffer);
864
        return;
865
    }
866

867
    var data = await this.get_buffer(id);
868

869
    if (!data || data.length < (offset+count)) {
870
        await this.ChangeSize(id, Math.floor(((offset+count)*3)/2));
871
        inode.size = offset + count;
872
        data = await this.get_buffer(id);
873
    } else
874
    if (inode.size < (offset+count)) {
875
        inode.size = offset + count;
876
    }
877
    if(buffer)
878
    {
879
        data.set(buffer.subarray(0, count), offset);
880
    }
881
    await this.set_data(id, data);
882
};
883

884
FS.prototype.Read = async function(inodeid, offset, count)
885
{
886
    const inode = this.inodes[inodeid];
887
    if(this.is_forwarder(inode))
888
    {
889
        const foreign_id = inode.foreign_id;
890
        return await this.follow_fs(inode).Read(foreign_id, offset, count);
891
    }
892

893
    return await this.get_data(inodeid, offset, count);
894
};
895

896
FS.prototype.Search = function(parentid, name) {
897
    const parent_inode = this.inodes[parentid];
898

899
    if(this.is_forwarder(parent_inode))
900
    {
901
        const foreign_parentid = parent_inode.foreign_id;
902
        const foreign_id = this.follow_fs(parent_inode).Search(foreign_parentid, name);
903
        if(foreign_id === -1) return -1;
904
        return this.get_forwarder(parent_inode.mount_id, foreign_id);
905
    }
906

907
    const childid = parent_inode.direntries.get(name);
908
    return childid === undefined ? -1 : childid;
909
};
910

911
FS.prototype.CountUsedInodes = function()
912
{
913
    let count = this.inodes.length;
914
    for(const { fs, backtrack } of this.mounts)
915
    {
916
        count += fs.CountUsedInodes();
917

918
        // Forwarder inodes don't count.
919
        count -=  backtrack.size;
920
    }
921
    return count;
922
};
923

924
FS.prototype.CountFreeInodes = function()
925
{
926
    let count = 1024 * 1024;
927
    for(const { fs } of this.mounts)
928
    {
929
        count += fs.CountFreeInodes();
930
    }
931
    return count;
932
};
933

934
FS.prototype.GetTotalSize = function() {
935
    let size = this.used_size;
936
    for(const { fs } of this.mounts)
937
    {
938
        size += fs.GetTotalSize();
939
    }
940
    return size;
941
    //var size = 0;
942
    //for(var i=0; i<this.inodes.length; i++) {
943
    //    var d = this.inodes[i].data;
944
    //    size += d ? d.length : 0;
945
    //}
946
    //return size;
947
};
948

949
FS.prototype.GetSpace = function() {
950
    let size = this.total_size;
951
    for(const { fs } of this.mounts)
952
    {
953
        size += fs.GetSpace();
954
    }
955
    return this.total_size;
956
};
957

958
/**
959
 * XXX: Not ideal.
960
 * @param {number} idx
961
 * @return {string}
962
 */
963
FS.prototype.GetDirectoryName = function(idx)
964
{
965
    const parent_inode = this.inodes[this.GetParent(idx)];
966

967
    if(this.is_forwarder(parent_inode))
968
    {
969
        return this.follow_fs(parent_inode).GetDirectoryName(this.inodes[idx].foreign_id);
970
    }
971

972
    // Root directory.
973
    if(!parent_inode) return "";
974

975
    for(const [name, childid] of parent_inode.direntries)
976
    {
977
        if(childid === idx) return name;
978
    }
979

980
    dbg_assert(false, "Filesystem: Found directory inode whose parent doesn't link to it");
981
    return "";
982
};
983

984
FS.prototype.GetFullPath = function(idx) {
985
    dbg_assert(this.IsDirectory(idx), "Filesystem: Cannot get full path of non-directory inode");
986

987
    var path = "";
988

989
    while(idx != 0) {
990
        path = "/" + this.GetDirectoryName(idx) + path;
991
        idx = this.GetParent(idx);
992
    }
993
    return path.substring(1);
994
};
995

996
/**
997
 * @param {number} parentid
998
 * @param {number} targetid
999
 * @param {string} name
1000
 * @return {number} 0 if success, or -errno if failured.
1001
 */
1002
FS.prototype.Link = function(parentid, targetid, name)
1003
{
1004
    if(this.IsDirectory(targetid))
1005
    {
1006
        return -EPERM;
1007
    }
1008

1009
    const parent_inode = this.inodes[parentid];
1010
    const inode = this.inodes[targetid];
1011

1012
    if(this.is_forwarder(parent_inode))
1013
    {
1014
        if(!this.is_forwarder(inode) || inode.mount_id !== parent_inode.mount_id)
1015
        {
1016
            dbg_log("XXX: Attempted to hardlink a file into a child filesystem - skipped", LOG_9P);
1017
            return -EPERM;
1018
        }
1019
        return this.follow_fs(parent_inode).Link(parent_inode.foreign_id, inode.foreign_id, name);
1020
    }
1021

1022
    if(this.is_forwarder(inode))
1023
    {
1024
        dbg_log("XXX: Attempted to hardlink file across filesystems - skipped", LOG_9P);
1025
        return -EPERM;
1026
    }
1027

1028
    this.link_under_dir(parentid, targetid, name);
1029
    return 0;
1030
};
1031

1032
FS.prototype.Unlink = function(parentid, name) {
1033
    if(name === "." || name === "..")
1034
    {
1035
        // Also guarantees that root cannot be deleted.
1036
        return -EPERM;
1037
    }
1038
    const idx = this.Search(parentid, name);
1039
    const inode = this.inodes[idx];
1040
    const parent_inode = this.inodes[parentid];
1041
    //message.Debug("Unlink " + inode.name);
1042

1043
    // forward if necessary
1044
    if(this.is_forwarder(parent_inode))
1045
    {
1046
        dbg_assert(this.is_forwarder(inode), "Children of forwarders should be forwarders");
1047

1048
        const foreign_parentid = parent_inode.foreign_id;
1049
        return this.follow_fs(parent_inode).Unlink(foreign_parentid, name);
1050

1051
        // Keep the forwarder dangling - file is still accessible.
1052
    }
1053

1054
    if(this.IsDirectory(idx) && !this.IsEmpty(idx))
1055
    {
1056
        return -ENOTEMPTY;
1057
    }
1058

1059
    this.unlink_from_dir(parentid, name);
1060

1061
    if(inode.nlinks === 0)
1062
    {
1063
        // don't delete the content. The file is still accessible
1064
        inode.status = STATUS_UNLINKED;
1065
        this.NotifyListeners(idx, 'delete');
1066
    }
1067
    return 0;
1068
};
1069

1070
FS.prototype.DeleteData = async function(idx)
1071
{
1072
    const inode = this.inodes[idx];
1073
    if(this.is_forwarder(inode))
1074
    {
1075
        await this.follow_fs(inode).DeleteData(inode.foreign_id);
1076
        return;
1077
    }
1078
    inode.size = 0;
1079
    delete this.inodedata[idx];
1080
};
1081

1082
/**
1083
 * @private
1084
 * @param {number} idx
1085
 * @return {!Promise<Uint8Array>} The buffer that contains the file contents, which may be larger
1086
 *      than the data itself. To ensure that any modifications done to this buffer is reflected
1087
 *      to the file, call set_data with the modified buffer.
1088
 */
1089
FS.prototype.get_buffer = async function(idx)
1090
{
1091
    const inode = this.inodes[idx];
1092
    dbg_assert(inode, `Filesystem get_buffer: idx ${idx} does not point to an inode`);
1093

1094
    if(this.inodedata[idx])
1095
    {
1096
        return this.inodedata[idx];
1097
    }
1098
    else if(inode.status === STATUS_ON_STORAGE)
1099
    {
1100
        dbg_assert(inode.sha256sum, "Filesystem get_data: found inode on server without sha256sum");
1101
        return await this.storage.read(inode.sha256sum, 0, inode.size);
1102
    }
1103
    else
1104
    {
1105
        return null;
1106
    }
1107
};
1108

1109
/**
1110
 * @private
1111
 * @param {number} idx
1112
 * @param {number} offset
1113
 * @param {number} count
1114
 * @return {!Promise<Uint8Array>}
1115
 */
1116
FS.prototype.get_data = async function(idx, offset, count)
1117
{
1118
    const inode = this.inodes[idx];
1119
    dbg_assert(inode, `Filesystem get_data: idx ${idx} does not point to an inode`);
1120

1121
    if(this.inodedata[idx])
1122
    {
1123
        return this.inodedata[idx].subarray(offset, offset + count);
1124
    }
1125
    else if(inode.status === STATUS_ON_STORAGE)
1126
    {
1127
        dbg_assert(inode.sha256sum, "Filesystem get_data: found inode on server without sha256sum");
1128
        return await this.storage.read(inode.sha256sum, offset, count);
1129
    }
1130
    else
1131
    {
1132
        return null;
1133
    }
1134
};
1135

1136
/**
1137
 * @private
1138
 * @param {number} idx
1139
 * @param {Uint8Array} buffer
1140
 */
1141
FS.prototype.set_data = async function(idx, buffer)
1142
{
1143
    // Current scheme: Save all modified buffers into local inodedata.
1144
    this.inodedata[idx] = buffer;
1145
    if(this.inodes[idx].status === STATUS_ON_STORAGE)
1146
    {
1147
        this.inodes[idx].status = STATUS_OK;
1148
        this.storage.uncache(this.inodes[idx].sha256sum);
1149
    }
1150
};
1151

1152
/**
1153
 * @param {number} idx
1154
 * @return {!Inode}
1155
 */
1156
FS.prototype.GetInode = function(idx)
1157
{
1158
    dbg_assert(!isNaN(idx), "Filesystem GetInode: NaN idx");
1159
    dbg_assert(idx >= 0 && idx < this.inodes.length, "Filesystem GetInode: out of range idx:" + idx);
1160

1161
    const inode = this.inodes[idx];
1162
    if(this.is_forwarder(inode))
1163
    {
1164
        return this.follow_fs(inode).GetInode(inode.foreign_id);
1165
    }
1166

1167
    return inode;
1168
};
1169

1170
FS.prototype.ChangeSize = async function(idx, newsize)
1171
{
1172
    var inode = this.GetInode(idx);
1173
    var temp = await this.get_data(idx, 0, inode.size);
1174
    //message.Debug("change size to: " + newsize);
1175
    if (newsize == inode.size) return;
1176
    var data = new Uint8Array(newsize);
1177
    inode.size = newsize;
1178
    if(temp)
1179
    {
1180
        var size = Math.min(temp.length, inode.size);
1181
        data.set(temp.subarray(0, size), 0);
1182
    }
1183
    await this.set_data(idx, data);
1184
};
1185

1186
FS.prototype.SearchPath = function(path) {
1187
    //path = path.replace(/\/\//g, "/");
1188
    path = path.replace("//", "/");
1189
    var walk = path.split("/");
1190
    if (walk.length > 0 && walk[walk.length - 1].length === 0) walk.pop();
1191
    if (walk.length > 0 && walk[0].length === 0) walk.shift();
1192
    const n = walk.length;
1193

1194
    var parentid = -1;
1195
    var id = 0;
1196
    let forward_path = null;
1197
    for(var i=0; i<n; i++) {
1198
        parentid = id;
1199
        id = this.Search(parentid, walk[i]);
1200
        if(!forward_path && this.is_forwarder(this.inodes[parentid]))
1201
        {
1202
            forward_path = "/" + walk.slice(i).join("/");
1203
        }
1204
        if (id == -1) {
1205
            if (i < n-1) return {id: -1, parentid: -1, name: walk[i], forward_path }; // one name of the path cannot be found
1206
            return {id: -1, parentid: parentid, name: walk[i], forward_path}; // the last element in the path does not exist, but the parent
1207
        }
1208
    }
1209
    return {id: id, parentid: parentid, name: walk[i], forward_path};
1210
};
1211
// -----------------------------------------------------
1212

1213
/**
1214
 * @param {number} dirid
1215
 * @param {Array<{parentid: number, name: string}>} list
1216
 */
1217
FS.prototype.GetRecursiveList = function(dirid, list) {
1218
    if(this.is_forwarder(this.inodes[dirid]))
1219
    {
1220
        const foreign_fs = this.follow_fs(this.inodes[dirid]);
1221
        const foreign_dirid = this.inodes[dirid].foreign_id;
1222
        const mount_id = this.inodes[dirid].mount_id;
1223

1224
        const foreign_start = list.length;
1225
        foreign_fs.GetRecursiveList(foreign_dirid, list);
1226
        for(let i = foreign_start; i < list.length; i++)
1227
        {
1228
            list[i].parentid = this.get_forwarder(mount_id, list[i].parentid);
1229
        }
1230
        return;
1231
    }
1232
    for(const [name, id] of this.inodes[dirid].direntries)
1233
    {
1234
        if(name !== "." && name !== "..")
1235
        {
1236
            list.push({ parentid: dirid, name });
1237
            if(this.IsDirectory(id))
1238
            {
1239
                this.GetRecursiveList(id, list);
1240
            }
1241
        }
1242
    }
1243
};
1244

1245
FS.prototype.RecursiveDelete = function(path) {
1246
    var toDelete = [];
1247
    var ids = this.SearchPath(path);
1248
    if(ids.id === -1) return;
1249

1250
    this.GetRecursiveList(ids.id, toDelete);
1251

1252
    for(var i=toDelete.length-1; i>=0; i--)
1253
    {
1254
        const ret = this.Unlink(toDelete[i].parentid, toDelete[i].name);
1255
        dbg_assert(ret === 0, "Filesystem RecursiveDelete failed at parent=" + toDelete[i].parentid +
1256
            ", name='" + toDelete[i].name + "' with error code: " + (-ret));
1257
    }
1258
};
1259

1260
FS.prototype.DeleteNode = function(path) {
1261
    var ids = this.SearchPath(path);
1262
    if (ids.id == -1) return;
1263

1264
    if ((this.inodes[ids.id].mode&S_IFMT) == S_IFREG){
1265
        const ret = this.Unlink(ids.parentid, ids.name);
1266
        dbg_assert(ret === 0, "Filesystem DeleteNode failed with error code: " + (-ret));
1267
        return;
1268
    }
1269
    if ((this.inodes[ids.id].mode&S_IFMT) == S_IFDIR){
1270
        this.RecursiveDelete(path);
1271
        const ret = this.Unlink(ids.parentid, ids.name);
1272
        dbg_assert(ret === 0, "Filesystem DeleteNode failed with error code: " + (-ret));
1273
        return;
1274
    }
1275
};
1276

1277
/** @param {*=} info */
1278
FS.prototype.NotifyListeners = function(id, action, info) {
1279
    //if(info==undefined)
1280
    //    info = {};
1281

1282
    //var path = this.GetFullPath(id);
1283
    //if (this.watchFiles[path] == true && action=='write') {
1284
    //  message.Send("WatchFileEvent", path);
1285
    //}
1286
    //for (var directory of this.watchDirectories) {
1287
    //    if (this.watchDirectories.hasOwnProperty(directory)) {
1288
    //        var indexOf = path.indexOf(directory)
1289
    //        if(indexOf == 0 || indexOf == 1)
1290
    //            message.Send("WatchDirectoryEvent", {path: path, event: action, info: info});
1291
    //    }
1292
    //}
1293
};
1294

1295

1296
FS.prototype.Check = function() {
1297
    for(var i=1; i<this.inodes.length; i++)
1298
    {
1299
        if (this.inodes[i].status == STATUS_INVALID) continue;
1300

1301
        var inode = this.GetInode(i);
1302
        if (inode.nlinks < 0) {
1303
            message.Debug("Error in filesystem: negative nlinks=" + inode.nlinks + " at id =" + i);
1304
        }
1305

1306
        if(this.IsDirectory(i))
1307
        {
1308
            const inode = this.GetInode(i);
1309
            if(this.IsDirectory(i) && this.GetParent(i) < 0) {
1310
                message.Debug("Error in filesystem: negative parent id " + i);
1311
            }
1312
            for(const [name, id] of inode.direntries)
1313
            {
1314
                if(name.length === 0) {
1315
                    message.Debug("Error in filesystem: inode with no name and id " + id);
1316
                }
1317

1318
                for (const c of name) {
1319
                    if (c < 32) {
1320
                        message.Debug("Error in filesystem: Unallowed char in filename");
1321
                    }
1322
                }
1323
            }
1324
        }
1325
    }
1326

1327
};
1328

1329

1330
FS.prototype.FillDirectory = function(dirid) {
1331
    const inode = this.inodes[dirid];
1332
    if(this.is_forwarder(inode))
1333
    {
1334
        // XXX: The ".." of a mountpoint should point back to an inode in this fs.
1335
        // Otherwise, ".." gets the wrong qid and mode.
1336
        this.follow_fs(inode).FillDirectory(inode.foreign_id);
1337
        return;
1338
    }
1339

1340
    let size = 0;
1341
    for(const name of inode.direntries.keys())
1342
    {
1343
        size += 13 + 8 + 1 + 2 + UTF8.UTF8Length(name);
1344
    }
1345
    const data = this.inodedata[dirid] = new Uint8Array(size);
1346
    inode.size = size;
1347

1348
    let offset = 0x0;
1349
    for(const [name, id] of inode.direntries)
1350
    {
1351
        const child = this.GetInode(id);
1352
        offset += marshall.Marshall(
1353
            ["Q", "d", "b", "s"],
1354
            [child.qid,
1355
            offset+13+8+1+2+UTF8.UTF8Length(name),
1356
            child.mode >> 12,
1357
            name],
1358
            data, offset);
1359
    }
1360
};
1361

1362
FS.prototype.RoundToDirentry = function(dirid, offset_target)
1363
{
1364
    const data = this.inodedata[dirid];
1365
    dbg_assert(data, `FS directory data for dirid=${dirid} should be generated`);
1366
    dbg_assert(data.length, "FS directory should have at least an entry");
1367

1368
    if(offset_target >= data.length)
1369
    {
1370
        return data.length;
1371
    }
1372

1373
    let offset = 0;
1374
    while(true)
1375
    {
1376
        const next_offset = marshall.Unmarshall(["Q", "d"], data, { offset })[1];
1377
        if(next_offset > offset_target) break;
1378
        offset = next_offset;
1379
    }
1380

1381
    return offset;
1382
};
1383

1384
/**
1385
 * @param {number} idx
1386
 * @return {boolean}
1387
 */
1388
FS.prototype.IsDirectory = function(idx)
1389
{
1390
    const inode = this.inodes[idx];
1391
    if(this.is_forwarder(inode))
1392
    {
1393
        return this.follow_fs(inode).IsDirectory(inode.foreign_id);
1394
    }
1395
    return (inode.mode & S_IFMT) === S_IFDIR;
1396
};
1397

1398
/**
1399
 * @param {number} idx
1400
 * @return {boolean}
1401
 */
1402
FS.prototype.IsEmpty = function(idx)
1403
{
1404
    const inode = this.inodes[idx];
1405
    if(this.is_forwarder(inode))
1406
    {
1407
        return this.follow_fs(inode).IsDirectory(inode.foreign_id);
1408
    }
1409
    for(const name of inode.direntries.keys())
1410
    {
1411
        if(name !== "." && name !== "..") return false;
1412
    }
1413
    return true;
1414
};
1415

1416
/**
1417
 * @param {number} idx
1418
 * @return {!Array<string>} List of children names
1419
 */
1420
FS.prototype.GetChildren = function(idx)
1421
{
1422
    dbg_assert(this.IsDirectory(idx), "Filesystem: cannot get children of non-directory inode");
1423
    const inode = this.inodes[idx];
1424
    if(this.is_forwarder(inode))
1425
    {
1426
        return this.follow_fs(inode).GetChildren(inode.foreign_id);
1427
    }
1428
    const children = [];
1429
    for(const name of inode.direntries.keys())
1430
    {
1431
        if(name !== "." && name !== "..")
1432
        {
1433
            children.push(name);
1434
        }
1435
    }
1436
    return children;
1437
};
1438

1439
/**
1440
 * @param {number} idx
1441
 * @return {number} Local idx of parent
1442
 */
1443
FS.prototype.GetParent = function(idx)
1444
{
1445
    dbg_assert(this.IsDirectory(idx), "Filesystem: cannot get parent of non-directory inode");
1446

1447
    const inode = this.inodes[idx];
1448

1449
    if(this.should_be_linked(inode))
1450
    {
1451
        return inode.direntries.get("..");
1452
    }
1453
    else
1454
    {
1455
        const foreign_dirid = this.follow_fs(inode).GetParent(inode.foreign_id);
1456
        dbg_assert(foreign_dirid !== -1, "Filesystem: should not have invalid parent ids");
1457
        return this.get_forwarder(inode.mount_id, foreign_dirid);
1458
    }
1459
};
1460

1461

1462
// -----------------------------------------------------
1463

1464
// only support for security.capabilities
1465
// should return a  "struct vfs_cap_data" defined in
1466
// linux/capability for format
1467
// check also:
1468
//   sys/capability.h
1469
//   http://lxr.free-electrons.com/source/security/commoncap.c#L376
1470
//   http://man7.org/linux/man-pages/man7/capabilities.7.html
1471
//   http://man7.org/linux/man-pages/man8/getcap.8.html
1472
//   http://man7.org/linux/man-pages/man3/libcap.3.html
1473
FS.prototype.PrepareCAPs = function(id) {
1474
    var inode = this.GetInode(id);
1475
    if (inode.caps) return inode.caps.length;
1476
    inode.caps = new Uint8Array(20);
1477
    // format is little endian
1478
    // note: getxattr returns -EINVAL if using revision 1 format.
1479
    // note: getxattr presents revision 3 as revision 2 when revision 3 is not needed.
1480
    // magic_etc (revision=0x02: 20 bytes)
1481
    inode.caps[0]  = 0x00;
1482
    inode.caps[1]  = 0x00;
1483
    inode.caps[2]  = 0x00;
1484
    inode.caps[3]  = 0x02;
1485

1486
    // lower
1487
    // permitted (first 32 capabilities)
1488
    inode.caps[4]  = 0xFF;
1489
    inode.caps[5]  = 0xFF;
1490
    inode.caps[6]  = 0xFF;
1491
    inode.caps[7]  = 0xFF;
1492
    // inheritable (first 32 capabilities)
1493
    inode.caps[8]  = 0xFF;
1494
    inode.caps[9]  = 0xFF;
1495
    inode.caps[10] = 0xFF;
1496
    inode.caps[11] = 0xFF;
1497

1498
    // higher
1499
    // permitted (last 6 capabilities)
1500
    inode.caps[12] = 0x3F;
1501
    inode.caps[13] = 0x00;
1502
    inode.caps[14] = 0x00;
1503
    inode.caps[15] = 0x00;
1504
    // inheritable (last 6 capabilities)
1505
    inode.caps[16] = 0x3F;
1506
    inode.caps[17] = 0x00;
1507
    inode.caps[18] = 0x00;
1508
    inode.caps[19] = 0x00;
1509

1510
    return inode.caps.length;
1511
};
1512

1513
// -----------------------------------------------------
1514

1515
/**
1516
 * @constructor
1517
 * @param {FS} filesystem
1518
 */
1519
function FSMountInfo(filesystem)
1520
{
1521
    /** @type {FS}*/
1522
    this.fs = filesystem;
1523

1524
    /**
1525
     * Maps foreign inode id back to local inode id.
1526
     * @type {!Map<number,number>}
1527
     */
1528
    this.backtrack = new Map();
1529
}
1530

1531
FSMountInfo.prototype.get_state = function()
1532
{
1533
    const state = [];
1534

1535
    state[0] = this.fs;
1536
    state[1] = [...this.backtrack];
1537

1538
    return state;
1539
};
1540

1541
FSMountInfo.prototype.set_state = function(state)
1542
{
1543
    this.fs = state[0];
1544
    this.backtrack = new Map(state[1]);
1545
};
1546

1547
/**
1548
 * @private
1549
 * @param {number} idx Local idx of inode.
1550
 * @param {number} mount_id Mount number of the destination fs.
1551
 * @param {number} foreign_id Foreign idx of destination inode.
1552
 */
1553
FS.prototype.set_forwarder = function(idx, mount_id, foreign_id)
1554
{
1555
    const inode = this.inodes[idx];
1556

1557
    dbg_assert(inode.nlinks === 0,
1558
        "Filesystem: attempted to convert an inode into forwarder before unlinking the inode");
1559

1560
    if(this.is_forwarder(inode))
1561
    {
1562
        this.mounts[inode.mount_id].backtrack.delete(inode.foreign_id);
1563
    }
1564

1565
    inode.status = STATUS_FORWARDING;
1566
    inode.mount_id = mount_id;
1567
    inode.foreign_id = foreign_id;
1568

1569
    this.mounts[mount_id].backtrack.set(foreign_id, idx);
1570
};
1571

1572
/**
1573
 * @private
1574
 * @param {number} mount_id Mount number of the destination fs.
1575
 * @param {number} foreign_id Foreign idx of destination inode.
1576
 * @return {number} Local idx of newly created forwarder.
1577
 */
1578
FS.prototype.create_forwarder = function(mount_id, foreign_id)
1579
{
1580
    const inode = this.CreateInode();
1581

1582
    const idx = this.inodes.length;
1583
    this.inodes.push(inode);
1584
    inode.fid = idx;
1585

1586
    this.set_forwarder(idx, mount_id, foreign_id);
1587
    return idx;
1588
};
1589

1590
/**
1591
 * @private
1592
 * @param {Inode} inode
1593
 * @return {boolean}
1594
 */
1595
FS.prototype.is_forwarder = function(inode)
1596
{
1597
    return inode.status === STATUS_FORWARDING;
1598
};
1599

1600
/**
1601
 * Whether the inode it points to is a root of some filesystem.
1602
 * @private
1603
 * @param {number} idx
1604
 * @return {boolean}
1605
 */
1606
FS.prototype.is_a_root = function(idx)
1607
{
1608
    return this.GetInode(idx).fid === 0;
1609
};
1610

1611
/**
1612
 * Ensures forwarder exists, and returns such forwarder, for the described foreign inode.
1613
 * @private
1614
 * @param {number} mount_id
1615
 * @param {number} foreign_id
1616
 * @return {number} Local idx of a forwarder to described inode.
1617
 */
1618
FS.prototype.get_forwarder = function(mount_id, foreign_id)
1619
{
1620
    const mount = this.mounts[mount_id];
1621

1622
    dbg_assert(foreign_id >= 0, "Filesystem get_forwarder: invalid foreign_id: " + foreign_id);
1623
    dbg_assert(mount, "Filesystem get_forwarder: invalid mount number: " + mount_id);
1624

1625
    const result = mount.backtrack.get(foreign_id);
1626

1627
    if(result === undefined)
1628
    {
1629
        // Create if not already exists.
1630
        return this.create_forwarder(mount_id, foreign_id);
1631
    }
1632

1633
    return result;
1634
};
1635

1636
/**
1637
 * @private
1638
 * @param {Inode} inode
1639
 */
1640
FS.prototype.delete_forwarder = function(inode)
1641
{
1642
    dbg_assert(this.is_forwarder(inode), "Filesystem delete_forwarder: expected forwarder");
1643

1644
    inode.status = STATUS_INVALID;
1645
    this.mounts[inode.mount_id].backtrack.delete(inode.foreign_id);
1646
};
1647

1648
/**
1649
 * @private
1650
 * @param {Inode} inode
1651
 * @return {FS}
1652
 */
1653
FS.prototype.follow_fs = function(inode)
1654
{
1655
    const mount = this.mounts[inode.mount_id];
1656

1657
    dbg_assert(this.is_forwarder(inode),
1658
        "Filesystem follow_fs: inode should be a forwarding inode");
1659
    dbg_assert(mount, "Filesystem follow_fs: inode<id=" + inode.fid +
1660
        "> should point to valid mounted FS");
1661

1662
    return mount.fs;
1663
};
1664

1665
/**
1666
 * Mount another filesystem to given path.
1667
 * @param {string} path
1668
 * @param {FS} fs
1669
 * @return {number} inode id of mount point if successful, or -errno if mounting failed.
1670
 */
1671
FS.prototype.Mount = function(path, fs)
1672
{
1673
    dbg_assert(fs.qidcounter === this.qidcounter,
1674
        "Cannot mount filesystem whose qid numbers aren't synchronised with current filesystem.");
1675

1676
    const path_infos = this.SearchPath(path);
1677

1678
    if(path_infos.parentid === -1)
1679
    {
1680
        dbg_log("Mount failed: parent for path not found: " + path, LOG_9P);
1681
        return -ENOENT;
1682
    }
1683
    if(path_infos.id !== -1)
1684
    {
1685
        dbg_log("Mount failed: file already exists at path: " + path, LOG_9P);
1686
        return -EEXIST;
1687
    }
1688
    if(path_infos.forward_path)
1689
    {
1690
        const parent = this.inodes[path_infos.parentid];
1691
        const ret = this.follow_fs(parent).Mount(path_infos.forward_path, fs);
1692
        if(ret < 0) return ret;
1693
        return this.get_forwarder(parent.mount_id, ret);
1694
    }
1695

1696
    const mount_id = this.mounts.length;
1697
    this.mounts.push(new FSMountInfo(fs));
1698

1699
    const idx = this.create_forwarder(mount_id, 0);
1700
    this.link_under_dir(path_infos.parentid, idx, path_infos.name);
1701

1702
    return idx;
1703
};
1704

1705
/**
1706
 * @constructor
1707
 */
1708
function FSLockRegion()
1709
{
1710
    this.type = P9_LOCK_TYPE_UNLCK;
1711
    this.start = 0;
1712
    this.length = Infinity;
1713
    this.proc_id = -1;
1714
    this.client_id = "";
1715
}
1716

1717
FSLockRegion.prototype.get_state = function()
1718
{
1719
    const state = [];
1720

1721
    state[0] = this.type;
1722
    state[1] = this.start;
1723
    // Infinity is not JSON.stringify-able
1724
    state[2] = this.length === Infinity ? 0 : this.length;
1725
    state[3] = this.proc_id;
1726
    state[4] = this.client_id;
1727

1728
    return state;
1729
};
1730

1731
FSLockRegion.prototype.set_state = function(state)
1732
{
1733
    this.type = state[0];
1734
    this.start = state[1];
1735
    this.length = state[2] === 0 ? Infinity : state[2];
1736
    this.proc_id = state[3];
1737
    this.client_id = state[4];
1738
};
1739

1740
/**
1741
 * @return {FSLockRegion}
1742
 */
1743
FSLockRegion.prototype.clone = function()
1744
{
1745
    const new_region = new FSLockRegion();
1746
    new_region.set_state(this.get_state());
1747
    return new_region;
1748
};
1749

1750
/**
1751
 * @param {FSLockRegion} region
1752
 * @return {boolean}
1753
 */
1754
FSLockRegion.prototype.conflicts_with = function(region)
1755
{
1756
    if(this.proc_id === region.proc_id && this.client_id === region.client_id) return false;
1757
    if(this.type === P9_LOCK_TYPE_UNLCK || region.type === P9_LOCK_TYPE_UNLCK) return false;
1758
    if(this.type !== P9_LOCK_TYPE_WRLCK && region.type !== P9_LOCK_TYPE_WRLCK) return false;
1759
    if(this.start + this.length <= region.start) return false;
1760
    if(region.start + region.length <= this.start) return false;
1761
    return true;
1762
};
1763

1764
/**
1765
 * @param {FSLockRegion} region
1766
 * @return {boolean}
1767
 */
1768
FSLockRegion.prototype.is_alike = function(region)
1769
{
1770
    return region.proc_id === this.proc_id &&
1771
        region.client_id === this.client_id &&
1772
        region.type === this.type;
1773
};
1774

1775
/**
1776
 * @param {FSLockRegion} region
1777
 * @return {boolean}
1778
 */
1779
FSLockRegion.prototype.may_merge_after = function(region)
1780
{
1781
    return this.is_alike(region) && region.start + region.length === this.start;
1782
};
1783

1784
/**
1785
 * @param {number} type
1786
 * @param {number} start
1787
 * @param {number} length
1788
 * @param {number} proc_id
1789
 * @param {string} client_id
1790
 * @return {!FSLockRegion}
1791
 */
1792
FS.prototype.DescribeLock = function(type, start, length, proc_id, client_id)
1793
{
1794
    dbg_assert(type === P9_LOCK_TYPE_RDLCK ||
1795
        type === P9_LOCK_TYPE_WRLCK ||
1796
        type === P9_LOCK_TYPE_UNLCK,
1797
        "Filesystem: Invalid lock type: " + type);
1798
    dbg_assert(start >= 0, "Filesystem: Invalid negative lock starting offset: " + start);
1799
    dbg_assert(length > 0, "Filesystem: Invalid non-positive lock length: " + length);
1800

1801
    const lock = new FSLockRegion();
1802
    lock.type = type;
1803
    lock.start = start;
1804
    lock.length = length;
1805
    lock.proc_id = proc_id;
1806
    lock.client_id = client_id;
1807

1808
    return lock;
1809
};
1810

1811
/**
1812
 * @param {number} id
1813
 * @param {FSLockRegion} request
1814
 * @return {FSLockRegion} The first conflicting lock found, or null if requested lock is possible.
1815
 */
1816
FS.prototype.GetLock = function(id, request)
1817
{
1818
    const inode = this.inodes[id];
1819

1820
    if(this.is_forwarder(inode))
1821
    {
1822
        const foreign_id = inode.foreign_id;
1823
        return this.follow_fs(inode).GetLock(foreign_id, request);
1824
    }
1825

1826
    for(const region of inode.locks)
1827
    {
1828
        if(request.conflicts_with(region))
1829
        {
1830
            return region.clone();
1831
        }
1832
    }
1833
    return null;
1834
};
1835

1836
/**
1837
 * @param {number} id
1838
 * @param {FSLockRegion} request
1839
 * @param {number} flags
1840
 * @return {number} One of P9_LOCK_SUCCESS / P9_LOCK_BLOCKED / P9_LOCK_ERROR / P9_LOCK_GRACE.
1841
 */
1842
FS.prototype.Lock = function(id, request, flags)
1843
{
1844
    const inode = this.inodes[id];
1845

1846
    if(this.is_forwarder(inode))
1847
    {
1848
        const foreign_id = inode.foreign_id;
1849
        return this.follow_fs(inode).Lock(foreign_id, request, flags);
1850
    }
1851

1852
    request = request.clone();
1853

1854
    // (1) Check whether lock is possible before any modification.
1855
    if(request.type !== P9_LOCK_TYPE_UNLCK && this.GetLock(id, request))
1856
    {
1857
        return P9_LOCK_BLOCKED;
1858
    }
1859

1860
    // (2) Subtract requested region from locks of the same owner.
1861
    for(let i = 0; i < inode.locks.length; i++)
1862
    {
1863
        const region = inode.locks[i];
1864

1865
        dbg_assert(region.length > 0,
1866
            "Filesystem: Found non-positive lock region length: " + region.length);
1867
        dbg_assert(region.type === P9_LOCK_TYPE_RDLCK || region.type === P9_LOCK_TYPE_WRLCK,
1868
            "Filesystem: Found invalid lock type: " + region.type);
1869
        dbg_assert(!inode.locks[i-1] || inode.locks[i-1].start <= region.start,
1870
            "Filesystem: Locks should be sorted by starting offset");
1871

1872
        // Skip to requested region.
1873
        if(region.start + region.length <= request.start) continue;
1874

1875
        // Check whether we've skipped past the requested region.
1876
        if(request.start + request.length <= region.start) break;
1877

1878
        // Skip over locks of different owners.
1879
        if(region.proc_id !== request.proc_id || region.client_id !== request.client_id)
1880
        {
1881
            dbg_assert(!region.conflicts_with(request),
1882
                "Filesytem: Found conflicting lock region, despite already checked for conflicts");
1883
            continue;
1884
        }
1885

1886
        // Pretend region would be split into parts 1 and 2.
1887
        const start1 = region.start;
1888
        const start2 = request.start + request.length;
1889
        const length1 = request.start - start1;
1890
        const length2 = region.start + region.length - start2;
1891

1892
        if(length1 > 0 && length2 > 0 && region.type === request.type)
1893
        {
1894
            // Requested region is already locked with the required type.
1895
            // Return early - no need to modify anything.
1896
            return P9_LOCK_SUCCESS;
1897
        }
1898

1899
        if(length1 > 0)
1900
        {
1901
            // Shrink from right / first half of the split.
1902
            region.length = length1;
1903
        }
1904

1905
        if(length1 <= 0 && length2 > 0)
1906
        {
1907
            // Shrink from left.
1908
            region.start = start2;
1909
            region.length = length2;
1910
        }
1911
        else if(length2 > 0)
1912
        {
1913
            // Add second half of the split.
1914

1915
            // Fast-forward to correct location.
1916
            while(i < inode.locks.length && inode.locks[i].start < start2) i++;
1917

1918
            inode.locks.splice(i, 0,
1919
                this.DescribeLock(region.type, start2, length2, region.proc_id, region.client_id));
1920
        }
1921
        else if(length1 <= 0)
1922
        {
1923
            // Requested region completely covers this region. Delete.
1924
            inode.locks.splice(i, 1);
1925
            i--;
1926
        }
1927
    }
1928

1929
    // (3) Insert requested lock region as a whole.
1930
    // No point in adding the requested lock region as fragmented bits in the above loop
1931
    // and having to merge them all back into one.
1932
    if(request.type !== P9_LOCK_TYPE_UNLCK)
1933
    {
1934
        let new_region = request;
1935
        let has_merged = false;
1936
        let i = 0;
1937

1938
        // Fast-forward to requested position, and try merging with previous region.
1939
        for(; i < inode.locks.length; i++)
1940
        {
1941
            if(new_region.may_merge_after(inode.locks[i]))
1942
            {
1943
                inode.locks[i].length += request.length;
1944
                new_region = inode.locks[i];
1945
                has_merged = true;
1946
            }
1947
            if(request.start <= inode.locks[i].start) break;
1948
        }
1949

1950
        if(!has_merged)
1951
        {
1952
            inode.locks.splice(i, 0, new_region);
1953
            i++;
1954
        }
1955

1956
        // Try merging with the subsequent alike region.
1957
        for(; i < inode.locks.length; i++)
1958
        {
1959
            if(!inode.locks[i].is_alike(new_region)) continue;
1960

1961
            if(inode.locks[i].may_merge_after(new_region))
1962
            {
1963
                new_region.length += inode.locks[i].length;
1964
                inode.locks.splice(i, 1);
1965
            }
1966

1967
            // No more mergable regions after this.
1968
            break;
1969
        }
1970
    }
1971

1972
    return P9_LOCK_SUCCESS;
1973
};
1974

1975
FS.prototype.read_dir = function(path)
1976
{
1977
    const p = this.SearchPath(path);
1978

1979
    if(p.id === -1)
1980
    {
1981
        return undefined;
1982
    }
1983

1984
    const dir = this.GetInode(p.id);
1985

1986
    return Array.from(dir.direntries.keys()).filter(path => path !== "." && path !== "..");
1987
};
1988

1989
FS.prototype.read_file = function(file)
1990
{
1991
    const p = this.SearchPath(file);
1992

1993
    if(p.id === -1)
1994
    {
1995
        return Promise.resolve(null);
1996
    }
1997

1998
    const inode = this.GetInode(p.id);
1999

2000
    return this.Read(p.id, 0, inode.size);
2001
};
2002