summaryrefslogtreecommitdiff
path: root/util/cbfstool/fmd.c
blob: bfce0490cd44a83c4f377d94ab50e08599880e86 (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
/*
 * fmd.c, parser frontend and utility functions for flashmap descriptor language
 *
 * Copyright (C) 2015 Google, Inc.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; version 2 of the License.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA, 02110-1301 USA
 */

#include "fmd.h"

#include "fmd_parser.h"
#include "fmd_scanner.h"
#include "option.h"

#include <assert.h>
#include <search.h>
#include <string.h>

/*
 * Validate the given flashmap descriptor node's properties. In particular:
 *  - Ensure its name is globally unique.
 *  - Ensure its offset, if known, isn't located before the end of the previous
 *    section, if this can be determined.
 *  - Ensure its offset, if known, isn't located after the beginning of the next
 *    section or off the end of its parent section, if this can be determined.
 *  - Ensure its size is nonzero.
 *  - Ensure that the combination of its size and offset, if they are both
 *    known, doesn't place its end after the beginning of the next section or
 *    off the end of its parent section, if this can be determined.
 * In the case of a validation error, the particular problem is reported to
 * standard error and this function returns false. It should be noted that this
 * function makes no claim that the members of the node's child list are valid:
 * under no circumstances is any recursive validation performed.
 *
 * @param node  The flashmap descriptor node to be validated
 * @param start Optional minimum permissible base of the section to be
 *              validated, to be provided if known
 * @param end   Optional maximum permissible offset to the end of the section to
 *              be validated, to be provided if known
 * @return      Whether the node is valid
 */
static bool validate_descriptor_node(const struct flashmap_descriptor *node,
		struct unsigned_option start, struct unsigned_option end) {
	assert(node);

	ENTRY search_key = {node->name, NULL};
	if (hsearch(search_key, FIND)) {
		fprintf(stderr, "ERROR: Multiple sections with name '%s'\n",
								node->name);
		return false;
	}
	if (!hsearch(search_key, ENTER))
		assert(false);

	if (node->offset_known) {
		if (start.val_known && node->offset < start.val) {
			fprintf(stderr, "ERROR: Section '%s' starts too low\n",
								node->name);
			return false;
		} else if (end.val_known && node->offset > end.val) {
			fprintf(stderr, "ERROR: Section '%s' starts too high\n",
								node->name);
			return false;
		}
	}

	if (node->size_known) {
		if (node->size == 0) {
			fprintf(stderr, "ERROR: Section '%s' given no space\n",
								node->name);
			return false;
		} else if (node->offset_known) {
			unsigned node_end = node->offset + node->size;
			if (end.val_known && node_end > end.val) {
				fprintf(stderr, "ERROR: Section '%s' too big\n",
								node->name);
				return false;
			}
		}
	}

	return true;
}

/*
 * Performs reverse lateral processing of sibling nodes, as described by the
 * documentation of its caller, validate_and_complete_info(). If it encounters
 * a node that is invalid in a way that couldn't have been discovered earlier,
 * it explains the problem to standard output and returns false.
 *
 * @param first_incomplete_it First node whose offset or size couldn't be
 *                            determined during forward processing
 * @param cur_incomplete_it   Last node whose offset or size is unknown
 * @param end_watermark       Offset to the end of the unresolved region
 * @return                    Whether all completed nodes were still valid
 */
static bool complete_missing_info_backward(
			flashmap_descriptor_iterator_t first_incomplete_it,
			flashmap_descriptor_iterator_t cur_incomplete_it,
							unsigned end_watermark)
{
	assert(first_incomplete_it);
	assert(cur_incomplete_it);
	assert(cur_incomplete_it >= first_incomplete_it);

	do {
		struct flashmap_descriptor *cur = *cur_incomplete_it;

		assert(cur->offset_known || cur->size_known);
		if (!cur->offset_known) {
			if (cur->size > end_watermark) {
				fprintf(stderr, "ERROR: Section '%s' too big\n",
								cur->name);
				return false;
			}
			cur->offset_known = true;
			cur->offset = end_watermark -= cur->size;
		} else if (!cur->size_known) {
			if (cur->offset > end_watermark) {
				fprintf(stderr,
					"ERROR: Section '%s' starts too high\n",
								cur->name);
				return false;
			}
			cur->size_known = true;
			cur->size = end_watermark - cur->offset;
			end_watermark = cur->offset;
		}
	} while (--cur_incomplete_it >= first_incomplete_it);

	return true;
}

/*
 * Recursively examine each descendant of the provided flashmap descriptor node
 * to ensure its position and size are known, attempt to infer them otherwise,
 * and validate their values once they've been populated.
 * This processes nodes according to the following algorithm:
 *  - At each level of the tree, it moves laterally between siblings, keeping
 *    a watermark of its current offset relative to the previous section, which
 *    it uses to fill in any unknown offsets it encounters along the way.
 *  - The first time it encounters a sibling with unknown size, it loses track
 *    of the watermark, and is therefore unable to complete further offsets;
 *    instead, if the watermark was known before, it marks the current node as
 *    the first that couldn't be completed in the initial pass.
 *  - If the current watermark is unknown (i.e. a node has been marked as the
 *    first incomplete one) and one with a fixed offset is encountered, a
 *    reverse lateral traversal is dispatched that uses that provided offset as
 *    a reverse watermark to complete all unknown fields until it finishes with
 *    the node marked as the first incomplete one: at this point, that flag is
 *    cleared, the watermark is updated, and forward processing resumes from
 *    where it left off.
 *  - If the watermark is unknown (i.e. node(s) are incomplete) after traversing
 *    all children of a particular parent node, reverse processing is employed
 *    as described above, except that the reverse watermark is initialized to
 *    the parent node's size instead of the (nonexistent) next node's offset.
 *  - Once all of a node's children have been processed, the algorithm applies
 *    itself recursively to each of the child nodes; thus, lower levels of the
 *    tree are processed only after their containing levels are finished.
 * This approach can fail in two possible ways (in which case the problem is
 * reported to standard output and this function returns false):
 *  - Processing reveals that some node's provided value is invalid in some way.
 *  - Processing determines that one or more provided values require an omitted
 *    field to take a nonsensical value.
 *  - Processing determines that it is impossible to determine a group of
 *    omitted values. This state is detected when a node whose offset *and*
 *    value are omitted is encountered during forward processing and while the
 *    current watermark is unknown: in such a case, neither can be known without
 *    being provided with either the other or more context.
 * The function notably performs neither validation nor completion on the parent
 * node it is passed; thus, it is important to ensure that that node is valid.
 * (At the very least, it must have a valid size field in order for the
 * algorithm to work on its children.)
 *
 * @param cur_level Parent node, which must minimally already have a valid size
 * @return          Whether completing and validating the children succeeded
 */
static bool validate_and_complete_info(struct flashmap_descriptor *cur_level)
{
	assert(cur_level);
	assert(cur_level->size_known);

	// Our watermark is only known when first_incomplete_it is NULL.
	flashmap_descriptor_iterator_t first_incomplete_it = NULL;
	unsigned watermark = 0;

	fmd_foreach_child_iterator(cur_it, cur_level) {
		struct flashmap_descriptor *cur_section = *cur_it;

		if (first_incomplete_it) {
			if (cur_section->offset_known) {
				if (complete_missing_info_backward(
						first_incomplete_it, cur_it - 1,
							cur_section->offset)) {
					first_incomplete_it = NULL;
					watermark = cur_section->offset;
				} else {
					return false;
				}
			}
			// Otherwise, we can't go back until a provided offset.
		} else if (!cur_section->offset_known) {
			cur_section->offset_known = true;
			cur_section->offset = watermark;
		}

		assert(cur_level->size_known);
		struct unsigned_option max_endpoint = {true, cur_level->size};
		if (cur_it != cur_level->list + cur_level->list_len - 1) {
			struct flashmap_descriptor *next_section = cur_it[1];
			max_endpoint.val_known = next_section->offset_known;
			max_endpoint.val = next_section->offset;
		}
		if (!validate_descriptor_node(cur_section,
							(struct unsigned_option)
					{!first_incomplete_it, watermark},
								max_endpoint))
			return false;

		if (!cur_section->size_known) {
			if (!cur_section->offset_known) {
				fprintf(stderr,
					"ERROR: Cannot determine either offset or size of section '%s'\n",
							cur_section->name);
				return false;
			} else if (!first_incomplete_it) {
				first_incomplete_it = cur_it;
			} else {
				// We shouldn't find an unknown size within an
				// incomplete region because the backward
				// traversal at the beginning of this node's
				// processing should have concluded said region.
				assert(!first_incomplete_it);
			}
		} else if (!first_incomplete_it) {
			watermark = cur_section->offset + cur_section->size;
		}
	}

	if (first_incomplete_it &&
			!complete_missing_info_backward(first_incomplete_it,
				cur_level->list + cur_level->list_len - 1,
							cur_level->size))
		return false;

	fmd_foreach_child(cur_section, cur_level) {
		assert(cur_section->offset_known);
		assert(cur_section->size_known);

		if (!validate_and_complete_info(cur_section))
			return false;
	}

	return true;
}

static void print_with_prefix(const struct flashmap_descriptor *tree,
								const char *pre)
{
	assert(tree);
	assert(pre);

	printf("%ssection '%s' has ", pre, tree->name);

	if (tree->offset_known)
		printf("offset %uB, ", tree->offset);
	else
		fputs("unknown offset, ", stdout);

	if (tree->size_known)
		printf("size %uB, ", tree->size);
	else
		fputs("unknown size, ", stdout);

	printf("and %zu subsections", tree->list_len);
	if (tree->list_len) {
		puts(":");

		char child_prefix[strlen(pre) + 1];
		strcpy(child_prefix, pre);
		strcat(child_prefix, "\t");
		fmd_foreach_child(each, tree)
			print_with_prefix(each, child_prefix);
	} else {
		puts("");
	}
}

struct flashmap_descriptor *fmd_create(FILE *stream)
{
	assert(stream);

	yyin = stream;

	struct flashmap_descriptor *ret = NULL;
	if (yyparse() == 0)
		ret = res;

	yylex_destroy();
	yyin = NULL;
	res = NULL;

	if (ret) {
		// This hash table is used to store the declared name of each
		// section and ensure that each is globally unique.
		if (!hcreate(fmd_count_nodes(ret))) {
			perror("ERROR: While initializing hashtable");
			fmd_cleanup(ret);
			return NULL;
		}

		// Even though we haven't checked that the root node (ret) has
		// a size field as required by this function, the parser
		// warrants that it does because the grammar requires it.
		if (!validate_and_complete_info(ret)) {
			hdestroy();
			fmd_cleanup(ret);
			return NULL;
		}

		hdestroy();
	}

	return ret;
}

void fmd_cleanup(struct flashmap_descriptor *victim)
{
	if (!victim)
		return;

	free(victim->name);
	for (unsigned idx = 0; idx < victim->list_len; ++idx)
		fmd_cleanup(victim->list[idx]);
	free(victim->list);
	free(victim);
}

size_t fmd_count_nodes(const struct flashmap_descriptor *tree)
{
	assert(tree);

	if (!tree->list_len)
		return 1;

	unsigned count = 1;
	fmd_foreach_child(lower, tree)
		count += fmd_count_nodes(lower);
	return count;
}

const struct flashmap_descriptor *fmd_find_node(
		const struct flashmap_descriptor *root, const char *name)
{
	assert(root);
	assert(name);

	if (strcmp(root->name, name) == 0)
		return root;

	fmd_foreach_child(descendant, root) {
		const struct flashmap_descriptor *match =
						fmd_find_node(descendant, name);
		if (match)
			return match;
	}
	return NULL;
}

unsigned fmd_calc_absolute_offset(const struct flashmap_descriptor *root,
							const char *name)
{
	assert(root);
	assert(name);

	if (strcmp(root->name, name) == 0)
		return 0;

	fmd_foreach_child(descendant, root) {
		unsigned subtotal = fmd_calc_absolute_offset(descendant, name);
		if (subtotal != FMD_NOTFOUND)
			return descendant->offset + subtotal;
	}
	return FMD_NOTFOUND;
}

void fmd_print(const struct flashmap_descriptor *tree)
{
	print_with_prefix(tree, "");
}