aboutsummaryrefslogtreecommitdiff
path: root/include/fstree.h
blob: e8324a9c541478b641ca2d87e9dbc159c0202aff (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
/* SPDX-License-Identifier: GPL-3.0-or-later */
#ifndef FSTREE_H
#define FSTREE_H

#include <sys/types.h>
#include <sys/stat.h>
#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>

#include "str_table.h"

#define FSTREE_XATTR_KEY_BUCKETS 31
#define FSTREE_XATTR_VALUE_BUCKETS 511

typedef struct tree_node_t tree_node_t;
typedef struct file_info_t file_info_t;
typedef struct dir_info_t dir_info_t;
typedef struct fstree_t fstree_t;
typedef struct tree_xattr_t tree_xattr_t;

/**
 * @struct tree_xattr_t
 *
 * @brief Encapsulates a set of key-value pairs attached to a @ref tree_node_t
 */
struct tree_xattr_t {
	size_t num_attr;
	size_t max_attr;

	uint32_t block;
	uint32_t offset;
	uint32_t size;

	/**
	 * @brief Incremental index within all xattr blocks
	 */
	size_t index;

	/**
	 * @brief Back reference to the tree node this was created for
	 */
	tree_node_t *owner;

	/**
	 * @brief linked list pointer of list of attributes in @ref fstree_t
	 */
	tree_xattr_t *next;

	/**
	 * @brief An array with pairs of key-value tupples
	 *
	 * Each key-value tupple is encoded as (key << 32) | value.
	 */
	uint64_t ref[];
};

/**
 * @struct file_info_t
 *
 * @brief Additional meta data stored in a @ref tree_node_t for regular files
 */
struct file_info_t {
	char *input_file;

	/**
	 * @brief Linked list pointer for aggregating fragments
	 *
	 * When writing out data blocks, files that don't have a multiple of
	 * the block size have their tail ends gathered in a fragment block.
	 * A linked list is used to keep track of which files share the same
	 * fragment block.
	 */
	file_info_t *frag_next;

	/**
	 * @brief Total size of the file in bytes
	 */
	uint64_t size;

	/**
	 * @brief Absolute position of the first data block
	 */
	uint64_t startblock;

	/**
	 * @brief Fragment index
	 *
	 * If the size is not a multiple of the block size, this holds an
	 * index into the fragment table.
	 */
	uint32_t fragment;

	/**
	 * @brief Byte offset into the fragment block
	 *
	 * If the size is not a multiple of the block size, this holds an
	 * offset into the fragment block.
	 */
	uint32_t fragment_offset;

	/**
	 * @brief Stores the compressed file block sizes
	 *
	 * For each full data block, stores the compressed size. Bit number
	 * 24 is set if the block is stored uncompressed.
	 */
	uint32_t blocksizes[];
};

/**
 * @struct dir_info_t
 *
 * @brief Additional meta data stored in a @ref tree_node_t for directories
 */
struct dir_info_t {
	/**
	 * @brief Pointer to the head of the linked list of children
	 */
	tree_node_t *children;

	/**
	 * @brief Size of the directory
	 *
	 * Computed and updated on the fly while writing directory
	 * meta data to disk.
	 */
	uint64_t size;

	/**
	 * @brief Start block offset, relative to directory table start
	 *
	 * Offset of the compressed meta data block where the directory
	 * listing is stored in the SquashFS image.
	 */
	uint64_t start_block;

	/**
	 * @brief Byte offset into the uncompressed meta data block
	 *
	 * Points at where in the meta data block the directory listing begins.
	 */
	uint32_t block_offset;

	/**
	 * @brief Set to true for implicitly generated directories
	 */
	bool created_implicitly;
};

/**
 * @struct tree_node_t
 *
 * @brief A node in a file system tree
 */
struct tree_node_t {
	/**
	 * @brief Linked list pointer to the next node in the same directory
	 */
	tree_node_t *next;

	/**
	 * @brief Pointer to directory node that this node is in
	 *
	 * This is NULL only for the root node
	 */
	tree_node_t *parent;

	/**
	 * @brief Pointer into the payload area where the node name is stored
	 *
	 * For the root node, this points to an empty string
	 */
	char *name;

	/**
	 * @brief A pointer to an extended attribute array or NULL if unused
	 */
	tree_xattr_t *xattr;

	uint32_t uid;
	uint32_t gid;
	uint16_t mode;

	/**
	 * @brief SquashFS inode refernce number
	 *
	 * This is computed and stored here on the fly when writing inodes
	 * generated from tree nodes to the SquashFS image.
	 *
	 * An inode reference is the 32 bit offset of the compressed meta data
	 * block, shifted left by 16 and ored with a 13 bit offset into the
	 * uncompressed meta data block.
	 */
	uint64_t inode_ref;

	/**
	 * @brief inode number
	 *
	 * This is computed and stored here on the fly when writing inodes
	 * generated from tree nodes to the SquashFS image.
	 */
	uint32_t inode_num;

	/**
	 * @brief SquashFS inode type used for this tree node
	 *
	 * This is computed and stored here on the fly when writing inodes
	 * generated from tree nodes to the SquashFS image. It can't be
	 * easily determined in advance since it depends also on the size
	 * of the node, which means for directories the size of the directory
	 * entries once written to disk.
	 *
	 * All code that actually processes tree nodes should use the mode
	 * field instead (mode & S_IFMT gives us the node type). It is stored
	 * here when generating inodes since we need it later on to generate
	 * directory entries.
	 */
	int type;

	union {
		/**
		 * @brief Pointer into payload area storing directory meta data
		 */
		dir_info_t *dir;

		/**
		 * @brief Pointer into payload area storing file meta data
		 */
		file_info_t *file;

		/**
		 * @brief Pointer into payload area storing symlink target
		 */
		char *slink_target;

		/**
		 * @brief A device number for device special files
		 */
		uint64_t devno;
	} data;

	/**
	 * @brief Additional data stored in the tree node
	 */
	uint8_t payload[];
};

/**
 * @struct fstree_t
 *
 * @brief Encapsulates a file system tree
 */
struct fstree_t {
	uint32_t default_uid;
	uint32_t default_gid;
	uint32_t default_mode;
	uint32_t default_mtime;
	size_t block_size;

	str_table_t xattr_keys;
	str_table_t xattr_values;

	tree_node_t *root;
	tree_xattr_t *xattr;
};

/**
 * @brief Initialize an fstree object
 *
 * @memberof fstree_t
 *
 * Initializing means copying over the default values and creating a root node.
 * On error, an error message is written to stderr.
 *
 * @param fs           A pointer to an uninitialized fstree object
 * @param block_size   The data block size for regular files
 * @param mtime        Default modification time stamp to use on all nodes
 * @param default_mode Default permission bits to use on implicitly created
 *                     directories.
 * @param default_uid  Default UID to set on implicitly created directories.
 * @param default_gid  Default GID to set on implicitly created directories.
 *
 * @return Zero on success, -1 on failure
 */
int fstree_init(fstree_t *fs, size_t block_size, uint32_t mtime,
		uint16_t default_mode, uint32_t default_uid,
		uint32_t default_gid);

/**
 * @brief Clean up an fstree object and free all memory it uses
 *
 * @memberof fstree_t
 *
 * This function also recursively frees all tree nodes.
 *
 * @param fs A pointer to an fstree object
 */
void fstree_cleanup(fstree_t *fs);

/**
 * @brief Add a generic node to an fstree object
 *
 * @memberof fstree_t
 *
 * The new node is inserted by path. If some components of the path don't
 * exist, they are created as directories with default permissions, like
 * mkdir -p would, and marked as implcitily created. A subsequent call that
 * tries to create an existing tree node will fail, except if the target
 * is an implicitly created directory node and the call tries to create it
 * as a directory. This will simply overwrite the permissions and ownership.
 * The implicitly created flag is then cleared and subsequent attempts to
 * create this directory again will also fail.
 *
 * This function does not print anything to stderr, instead it sets an
 * appropriate errno value.
 *
 * @param fs        A pointer to an fstree object
 * @param path      The path of the new object to insert
 * @param mode      Specifies both access permission and what kind of node
 *                  to create
 * @param uid       The user id that owns the new node
 * @param gid       The group id that owns the new node
 * @param extra_len An additional number of bytes to allocate for payload data
 *
 * @return A pointer to the new tree node or NULL on failure
 */
tree_node_t *fstree_add(fstree_t *fs, const char *path, uint16_t mode,
			uint32_t uid, uint32_t gid, size_t extra_len);

/**
 * @brief A wrappter around @ref fstree_add for regular files
 *
 * @memberof fstree_t
 *
 * This function internally computes the number of extra payload bytes
 * requiered and sets up the payload pointers propperly, as they are
 * different than for other types of nodes.
 *
 * @return A pointer to the new tree node or NULL on failure
 */
tree_node_t *fstree_add_file(fstree_t *fs, const char *path, uint16_t mode,
			     uint32_t uid, uint32_t gid, uint64_t filesz,
			     const char *input);

/**
 * @brief Add an extended attribute key value pair to a tree node
 *
 * @memberof fstree_t
 *
 * @param fs    A pointer to the fstree object
 * @param node  A pointer to the tree node to attach attributes to
 * @param key   The xattr key with namespace prefix
 * @param value The xattr value string
 *
 * @return Zero on success, -1 on failure (prints error to stderr)
 */
int fstree_add_xattr(fstree_t *fs, tree_node_t *node,
		     const char *key, const char *value);

/**
 * @brief Recompute index number of all xattr blocks
 *
 * @memberof fstree_t
 *
 * @param fs A pointer to the fstree object
 */
void fstree_xattr_reindex(fstree_t *fs);

/**
 * @brief Remove dupliciate xattr listings
 *
 * @memberof fstree_t
 *
 * If two tree nodes have pointers to distinct @ref tree_xattr_t listings that
 * turn out to be equivalent, throw one of the two away and make both nodes
 * point to the same instance.
 */
void fstree_xattr_deduplicate(fstree_t *fs);

/**
 * @brief Load an fstree from a text file describing it
 *
 * @memberof fstree_t
 *
 * This function parses the file format accepted by gensquashfs and restores
 * a file system tree from it.
 *
 * On failure, an error report with filename and line number is written
 * to stderr.
 *
 * @param fs       A pointer to an fstree object that is already initialized
 *                 prior to calling this function.
 * @param filename The path to the input file to process.
 *
 * @return Zero on success, -1 on failure.
 */
int fstree_from_file(fstree_t *fs, const char *filename);

/**
 * @brief Lexicographically sort all directory contents
 *
 * @memberof fstree_t
 *
 * @param fs A pointer to an fstree object
 */
void fstree_sort(fstree_t *fs);

/**
 * @brief Add labels from an SELinux labeling file to all tree nodes
 *
 * @memberof fstree_t
 *
 * @param fs       A pointer to an fstree object
 * @param filename The name of the SELinux context file
 *
 * @return Zero on success, -1 on failure
 */
int fstree_relabel_selinux(fstree_t *fs, const char *filename);

#endif /* FSTREE_H */