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