1#!/usr/bin/env python3
2
3import struct
4import binascii
5import sys
6import itertools as it
7
8TAG_TYPES = {
9    'splice':       (0x700, 0x400),
10    'create':       (0x7ff, 0x401),
11    'delete':       (0x7ff, 0x4ff),
12    'name':         (0x700, 0x000),
13    'reg':          (0x7ff, 0x001),
14    'dir':          (0x7ff, 0x002),
15    'superblock':   (0x7ff, 0x0ff),
16    'struct':       (0x700, 0x200),
17    'dirstruct':    (0x7ff, 0x200),
18    'ctzstruct':    (0x7ff, 0x202),
19    'inlinestruct': (0x7ff, 0x201),
20    'userattr':     (0x700, 0x300),
21    'tail':         (0x700, 0x600),
22    'softtail':     (0x7ff, 0x600),
23    'hardtail':     (0x7ff, 0x601),
24    'gstate':       (0x700, 0x700),
25    'movestate':    (0x7ff, 0x7ff),
26    'crc':          (0x700, 0x500),
27    'ccrc':         (0x780, 0x500),
28    'fcrc':         (0x7ff, 0x5ff),
29}
30
31class Tag:
32    def __init__(self, *args):
33        if len(args) == 1:
34            self.tag = args[0]
35        elif len(args) == 3:
36            if isinstance(args[0], str):
37                type = TAG_TYPES[args[0]][1]
38            else:
39                type = args[0]
40
41            if isinstance(args[1], str):
42                id = int(args[1], 0) if args[1] not in 'x.' else 0x3ff
43            else:
44                id = args[1]
45
46            if isinstance(args[2], str):
47                size = int(args[2], str) if args[2] not in 'x.' else 0x3ff
48            else:
49                size = args[2]
50
51            self.tag = (type << 20) | (id << 10) | size
52        else:
53            assert False
54
55    @property
56    def isvalid(self):
57        return not bool(self.tag & 0x80000000)
58
59    @property
60    def isattr(self):
61        return not bool(self.tag & 0x40000000)
62
63    @property
64    def iscompactable(self):
65        return bool(self.tag & 0x20000000)
66
67    @property
68    def isunique(self):
69        return not bool(self.tag & 0x10000000)
70
71    @property
72    def type(self):
73        return (self.tag & 0x7ff00000) >> 20
74
75    @property
76    def type1(self):
77        return (self.tag & 0x70000000) >> 20
78
79    @property
80    def type3(self):
81        return (self.tag & 0x7ff00000) >> 20
82
83    @property
84    def id(self):
85        return (self.tag & 0x000ffc00) >> 10
86
87    @property
88    def size(self):
89        return (self.tag & 0x000003ff) >> 0
90
91    @property
92    def dsize(self):
93        return 4 + (self.size if self.size != 0x3ff else 0)
94
95    @property
96    def chunk(self):
97        return self.type & 0xff
98
99    @property
100    def schunk(self):
101        return struct.unpack('b', struct.pack('B', self.chunk))[0]
102
103    def is_(self, type):
104        try:
105            if ' ' in type:
106                type1, type3 = type.split()
107                return (self.is_(type1) and
108                    (self.type & ~TAG_TYPES[type1][0]) == int(type3, 0))
109
110            return self.type == int(type, 0)
111
112        except (ValueError, KeyError):
113            return (self.type & TAG_TYPES[type][0]) == TAG_TYPES[type][1]
114
115    def mkmask(self):
116        return Tag(
117            0x700 if self.isunique else 0x7ff,
118            0x3ff if self.isattr else 0,
119            0)
120
121    def chid(self, nid):
122        ntag = Tag(self.type, nid, self.size)
123        if hasattr(self, 'off'):    ntag.off    = self.off
124        if hasattr(self, 'data'):   ntag.data   = self.data
125        if hasattr(self, 'ccrc'):   ntag.crc    = self.crc
126        if hasattr(self, 'erased'): ntag.erased = self.erased
127        return ntag
128
129    def typerepr(self):
130        if (self.is_('ccrc')
131                and getattr(self, 'ccrc', 0xffffffff) != 0xffffffff):
132            crc_status = ' (bad)'
133        elif self.is_('fcrc') and getattr(self, 'erased', False):
134            crc_status = ' (era)'
135        else:
136            crc_status = ''
137
138        reverse_types = {v: k for k, v in TAG_TYPES.items()}
139        for prefix in range(12):
140            mask = 0x7ff & ~((1 << prefix)-1)
141            if (mask, self.type & mask) in reverse_types:
142                type = reverse_types[mask, self.type & mask]
143                if prefix > 0:
144                    return '%s %#x%s' % (
145                        type, self.type & ((1 << prefix)-1), crc_status)
146                else:
147                    return '%s%s' % (type, crc_status)
148        else:
149            return '%02x%s' % (self.type, crc_status)
150
151    def idrepr(self):
152        return repr(self.id) if self.id != 0x3ff else '.'
153
154    def sizerepr(self):
155        return repr(self.size) if self.size != 0x3ff else 'x'
156
157    def __repr__(self):
158        return 'Tag(%r, %d, %d)' % (self.typerepr(), self.id, self.size)
159
160    def __lt__(self, other):
161        return (self.id, self.type) < (other.id, other.type)
162
163    def __bool__(self):
164        return self.isvalid
165
166    def __int__(self):
167        return self.tag
168
169    def __index__(self):
170        return self.tag
171
172class MetadataPair:
173    def __init__(self, blocks):
174        if len(blocks) > 1:
175            self.pair = [MetadataPair([block]) for block in blocks]
176            self.pair = sorted(self.pair, reverse=True)
177
178            self.data = self.pair[0].data
179            self.rev  = self.pair[0].rev
180            self.tags = self.pair[0].tags
181            self.ids  = self.pair[0].ids
182            self.log  = self.pair[0].log
183            self.all_ = self.pair[0].all_
184            return
185
186        self.pair = [self]
187        self.data = blocks[0]
188        block = self.data
189
190        self.rev, = struct.unpack('<I', block[0:4])
191        crc = binascii.crc32(block[0:4])
192        fcrctag = None
193        fcrcdata = None
194
195        # parse tags
196        corrupt = False
197        tag = Tag(0xffffffff)
198        off = 4
199        self.log = []
200        self.all_ = []
201        while len(block) - off >= 4:
202            ntag, = struct.unpack('>I', block[off:off+4])
203
204            tag = Tag((int(tag) ^ ntag) & 0x7fffffff)
205            tag.off = off + 4
206            tag.data = block[off+4:off+tag.dsize]
207            if tag.is_('ccrc'):
208                crc = binascii.crc32(block[off:off+2*4], crc)
209            else:
210                crc = binascii.crc32(block[off:off+tag.dsize], crc)
211            tag.crc = crc
212            off += tag.dsize
213
214            self.all_.append(tag)
215
216            if tag.is_('fcrc') and len(tag.data) == 8:
217                fcrctag = tag
218                fcrcdata = struct.unpack('<II', tag.data)
219            elif tag.is_('ccrc'):
220                # is valid commit?
221                if crc != 0xffffffff:
222                    corrupt = True
223                if not corrupt:
224                    self.log = self.all_.copy()
225                    # end of commit?
226                    if fcrcdata:
227                        fcrcsize, fcrc = fcrcdata
228                        fcrc_ = 0xffffffff ^ binascii.crc32(
229                            block[off:off+fcrcsize])
230                        if fcrc_ == fcrc:
231                            fcrctag.erased = True
232                            corrupt = True
233
234                # reset tag parsing
235                crc = 0
236                tag = Tag(int(tag) ^ ((tag.type & 1) << 31))
237                fcrctag = None
238                fcrcdata = None
239
240        # find active ids
241        self.ids = list(it.takewhile(
242            lambda id: Tag('name', id, 0) in self,
243            it.count()))
244
245        # find most recent tags
246        self.tags = []
247        for tag in self.log:
248            if tag.is_('crc') or tag.is_('splice'):
249                continue
250            elif tag.id == 0x3ff:
251                if tag in self and self[tag] is tag:
252                    self.tags.append(tag)
253            else:
254                # id could have change, I know this is messy and slow
255                # but it works
256                for id in self.ids:
257                    ntag = tag.chid(id)
258                    if ntag in self and self[ntag] is tag:
259                        self.tags.append(ntag)
260
261        self.tags = sorted(self.tags)
262
263    def __bool__(self):
264        return bool(self.log)
265
266    def __lt__(self, other):
267        # corrupt blocks don't count
268        if not self or not other:
269            return bool(other)
270
271        # use sequence arithmetic to avoid overflow
272        return not ((other.rev - self.rev) & 0x80000000)
273
274    def __contains__(self, args):
275        try:
276            self[args]
277            return True
278        except KeyError:
279            return False
280
281    def __getitem__(self, args):
282        if isinstance(args, tuple):
283            gmask, gtag = args
284        else:
285            gmask, gtag = args.mkmask(), args
286
287        gdiff = 0
288        for tag in reversed(self.log):
289            if (gmask.id != 0 and tag.is_('splice') and
290                    tag.id <= gtag.id - gdiff):
291                if tag.is_('create') and tag.id == gtag.id - gdiff:
292                    # creation point
293                    break
294
295                gdiff += tag.schunk
296
297            if ((int(gmask) & int(tag)) ==
298                    (int(gmask) & int(gtag.chid(gtag.id - gdiff)))):
299                if tag.size == 0x3ff:
300                    # deleted
301                    break
302
303                return tag
304
305        raise KeyError(gmask, gtag)
306
307    def _dump_tags(self, tags, f=sys.stdout, truncate=True):
308        f.write("%-8s  %-8s  %-13s %4s %4s" % (
309            'off', 'tag', 'type', 'id', 'len'))
310        if truncate:
311            f.write('  data (truncated)')
312        f.write('\n')
313
314        for tag in tags:
315            f.write("%08x: %08x  %-14s %3s %4s" % (
316                tag.off, tag,
317                tag.typerepr(), tag.idrepr(), tag.sizerepr()))
318            if truncate:
319                f.write("  %-23s  %-8s\n" % (
320                    ' '.join('%02x' % c for c in tag.data[:8]),
321                    ''.join(c if c >= ' ' and c <= '~' else '.'
322                        for c in map(chr, tag.data[:8]))))
323            else:
324                f.write("\n")
325                for i in range(0, len(tag.data), 16):
326                    f.write("  %08x: %-47s  %-16s\n" % (
327                        tag.off+i,
328                        ' '.join('%02x' % c for c in tag.data[i:i+16]),
329                        ''.join(c if c >= ' ' and c <= '~' else '.'
330                            for c in map(chr, tag.data[i:i+16]))))
331
332    def dump_tags(self, f=sys.stdout, truncate=True):
333        self._dump_tags(self.tags, f=f, truncate=truncate)
334
335    def dump_log(self, f=sys.stdout, truncate=True):
336        self._dump_tags(self.log, f=f, truncate=truncate)
337
338    def dump_all(self, f=sys.stdout, truncate=True):
339        self._dump_tags(self.all_, f=f, truncate=truncate)
340
341def main(args):
342    blocks = []
343    with open(args.disk, 'rb') as f:
344        for block in [args.block1, args.block2]:
345            if block is None:
346                continue
347            f.seek(block * args.block_size)
348            blocks.append(f.read(args.block_size)
349                .ljust(args.block_size, b'\xff'))
350
351    # find most recent pair
352    mdir = MetadataPair(blocks)
353
354    try:
355        mdir.tail = mdir[Tag('tail', 0, 0)]
356        if mdir.tail.size != 8 or mdir.tail.data == 8*b'\xff':
357            mdir.tail = None
358    except KeyError:
359        mdir.tail = None
360
361    print("mdir {%s} rev %d%s%s%s" % (
362        ', '.join('%#x' % b
363            for b in [args.block1, args.block2]
364            if b is not None),
365        mdir.rev,
366        ' (was %s)' % ', '.join('%d' % m.rev for m in mdir.pair[1:])
367        if len(mdir.pair) > 1 else '',
368        ' (corrupted!)' if not mdir else '',
369        ' -> {%#x, %#x}' % struct.unpack('<II', mdir.tail.data)
370        if mdir.tail else ''))
371    if args.all:
372        mdir.dump_all(truncate=not args.no_truncate)
373    elif args.log:
374        mdir.dump_log(truncate=not args.no_truncate)
375    else:
376        mdir.dump_tags(truncate=not args.no_truncate)
377
378    return 0 if mdir else 1
379
380if __name__ == "__main__":
381    import argparse
382    import sys
383    parser = argparse.ArgumentParser(
384        description="Dump useful info about metadata pairs in littlefs.")
385    parser.add_argument('disk',
386        help="File representing the block device.")
387    parser.add_argument('block_size', type=lambda x: int(x, 0),
388        help="Size of a block in bytes.")
389    parser.add_argument('block1', type=lambda x: int(x, 0),
390        help="First block address for finding the metadata pair.")
391    parser.add_argument('block2', nargs='?', type=lambda x: int(x, 0),
392        help="Second block address for finding the metadata pair.")
393    parser.add_argument('-l', '--log', action='store_true',
394        help="Show tags in log.")
395    parser.add_argument('-a', '--all', action='store_true',
396        help="Show all tags in log, included tags in corrupted commits.")
397    parser.add_argument('-T', '--no-truncate', action='store_true',
398        help="Don't truncate large amounts of data.")
399    sys.exit(main(parser.parse_args()))
400