tree.c (10956B)
1 #include "tree.h" 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <string.h> 6 7 #include "blake2b.h" 8 #include "dist_parse.h" 9 10 #define F_HASH 0x01u 11 #define F_TOP_BLOB 0x02u 12 #define F_PATH 0x04u 13 #define F_MODE 0x08u 14 #define F_SIZE 0x10u 15 #define F_FILE_BLOB 0x20u 16 #define F_ROOT 0x40u 17 18 typedef enum TreeSection { TREE_SEC_TOP, TREE_SEC_FILE } TreeSection; 19 20 int dist_tree_mode_parse(const char* s, uint8_t* out) { 21 if (!s || !out) return DIST_ERR; 22 if (strcmp(s, "-") == 0) { 23 *out = DIST_TREE_MODE_FILE; 24 return DIST_OK; 25 } 26 if (strcmp(s, "x") == 0) { 27 *out = DIST_TREE_MODE_EXEC; 28 return DIST_OK; 29 } 30 return DIST_ERR; 31 } 32 33 const char* dist_tree_mode_name(uint8_t mode) { 34 if (mode == DIST_TREE_MODE_FILE) return "-"; 35 if (mode == DIST_TREE_MODE_EXEC) return "x"; 36 return NULL; 37 } 38 39 int dist_tree_path_valid(const char* p) { 40 size_t start = 0, i; 41 if (!p || !p[0] || p[0] == '/') return 0; 42 for (i = 0;; ++i) { 43 char c = p[i]; 44 if (c == '\\' || c == ':' || c == '\n' || c == '\r') return 0; 45 if (c == '/' || c == '\0') { 46 size_t n = i - start; 47 if (n == 0) return 0; 48 if (n == 1 && p[start] == '.') return 0; 49 if (n == 2 && p[start] == '.' && p[start + 1] == '.') return 0; 50 if (c == '\0') return 1; 51 start = i + 1u; 52 } 53 } 54 } 55 56 static int entry_cmp(const void* ap, const void* bp) { 57 const DistTreeEntry* a = (const DistTreeEntry*)ap; 58 const DistTreeEntry* b = (const DistTreeEntry*)bp; 59 return strcmp(a->path, b->path); 60 } 61 62 int dist_tree_sort_validate(DistTree* tree, char* err, size_t errcap) { 63 size_t i; 64 if (!tree) return dist_set_err(err, errcap, "missing tree"); 65 if (tree->n_entries && !tree->entries) 66 return dist_set_err(err, errcap, "missing tree entries"); 67 qsort(tree->entries, tree->n_entries, sizeof tree->entries[0], entry_cmp); 68 for (i = 0; i < tree->n_entries; ++i) { 69 if (!dist_tree_path_valid(tree->entries[i].path)) 70 return dist_set_err(err, errcap, "unsafe tree path"); 71 if (!dist_tree_mode_name(tree->entries[i].mode)) 72 return dist_set_err(err, errcap, "bad tree mode"); 73 if (i > 0 && strcmp(tree->entries[i - 1u].path, tree->entries[i].path) == 0) 74 return dist_set_err(err, errcap, "duplicate tree path"); 75 } 76 return DIST_OK; 77 } 78 79 static int tree_validate_canonical(const DistTree* tree) { 80 size_t i; 81 if (!tree) return DIST_ERR; 82 if (tree->n_entries && !tree->entries) return DIST_ERR; 83 for (i = 0; i < tree->n_entries; ++i) { 84 if (!dist_tree_path_valid(tree->entries[i].path)) return DIST_ERR; 85 if (!dist_tree_mode_name(tree->entries[i].mode)) return DIST_ERR; 86 if (i > 0 && strcmp(tree->entries[i - 1u].path, tree->entries[i].path) >= 0) 87 return DIST_ERR; 88 } 89 return DIST_OK; 90 } 91 92 static int emit(KitWriter* out, const char* s) { 93 return kit_writer_write(out, s, strlen(s)) == KIT_OK ? DIST_OK : DIST_ERR; 94 } 95 96 static int emit_u64(KitWriter* out, const char* key, uint64_t v) { 97 char num[24]; 98 snprintf(num, sizeof num, "%llu", (unsigned long long)v); 99 return dist_emit_kv(out, key, num); 100 } 101 102 static int emit_hex(KitWriter* out, const char* key, const uint8_t* h) { 103 char hex[2 * DIST_BLAKE2B_LEN + 1]; 104 dist_hex_encode(hex, h, DIST_BLAKE2B_LEN); 105 return dist_emit_kv(out, key, hex); 106 } 107 108 int dist_tree_emit(const DistTree* tree, KitWriter* out) { 109 size_t i; 110 if (!out || tree_validate_canonical(tree) != DIST_OK) return DIST_ERR; 111 if (emit(out, DIST_TREE_MAGIC "\n") != DIST_OK) return DIST_ERR; 112 if (dist_emit_kv(out, "hash", DIST_TREE_HASH) != DIST_OK) return DIST_ERR; 113 if (dist_emit_kv(out, "blob", DIST_TREE_BLOB_FORMAT) != DIST_OK) 114 return DIST_ERR; 115 for (i = 0; i < tree->n_entries; ++i) { 116 const DistTreeEntry* e = &tree->entries[i]; 117 const char* mode = dist_tree_mode_name(e->mode); 118 if (!mode) return DIST_ERR; 119 if (emit(out, "\n[file]\n") != DIST_OK) return DIST_ERR; 120 if (dist_emit_kv(out, "path", e->path) != DIST_OK) return DIST_ERR; 121 if (dist_emit_kv(out, "mode", mode) != DIST_OK) return DIST_ERR; 122 if (emit_u64(out, "size", e->size) != DIST_OK) return DIST_ERR; 123 if (emit_hex(out, "blob", e->blob) != DIST_OK) return DIST_ERR; 124 if (emit_hex(out, "root", e->root) != DIST_OK) return DIST_ERR; 125 } 126 return DIST_OK; 127 } 128 129 static int hex_hash(const char* val, uint8_t out[DIST_BLAKE2B_LEN]) { 130 if (strlen(val) != 2u * DIST_BLAKE2B_LEN) return DIST_ERR; 131 return dist_hex_decode(out, val, DIST_BLAKE2B_LEN); 132 } 133 134 static int check_dup(uint32_t seen, uint32_t flag, char* err, size_t errcap) { 135 if (seen & flag) return dist_set_err(err, errcap, "duplicate tree field"); 136 return DIST_OK; 137 } 138 139 static int finalize_file(const DistTree* tree, uint32_t seen, char* err, 140 size_t errcap) { 141 const DistTreeEntry* e; 142 if ((seen & (F_PATH | F_MODE | F_SIZE | F_FILE_BLOB | F_ROOT)) != 143 (F_PATH | F_MODE | F_SIZE | F_FILE_BLOB | F_ROOT)) 144 return dist_set_err(err, errcap, "missing required [file] field"); 145 if (!tree || tree->n_entries == 0) 146 return dist_set_err(err, errcap, "missing file"); 147 e = &tree->entries[tree->n_entries - 1u]; 148 if (!dist_tree_path_valid(e->path)) 149 return dist_set_err(err, errcap, "unsafe tree path"); 150 if (!dist_tree_mode_name(e->mode)) 151 return dist_set_err(err, errcap, "bad tree mode"); 152 if (tree->n_entries > 1u) { 153 const char* prev = tree->entries[tree->n_entries - 2u].path; 154 int cmp = strcmp(prev, e->path); 155 if (cmp == 0) return dist_set_err(err, errcap, "duplicate tree path"); 156 if (cmp > 0) 157 return dist_set_err(err, errcap, "non-canonical tree ordering"); 158 } 159 return DIST_OK; 160 } 161 162 int dist_tree_parse(const uint8_t* data, size_t len, DistTree* out, char* err, 163 size_t errcap) { 164 size_t pos = 0; 165 int first = 1; 166 TreeSection sec = TREE_SEC_TOP; 167 uint32_t top_seen = 0; 168 uint32_t file_seen = 0; 169 170 if (!data || !out) return dist_set_err(err, errcap, "missing tree manifest"); 171 if (out->cap_entries && !out->entries) 172 return dist_set_err(err, errcap, "missing tree entries"); 173 out->n_entries = 0; 174 175 while (pos < len) { 176 char buf[DIST_KV_LINE_MAX]; 177 size_t end = pos; 178 size_t n, i; 179 char *t, *key, *val, *eq; 180 181 while (end < len && data[end] != '\n') ++end; 182 n = end - pos; 183 if (n >= sizeof buf) return dist_set_err(err, errcap, "line too long"); 184 for (i = pos; i < end; ++i) 185 if (data[i] == 0) 186 return dist_set_err(err, errcap, "NUL byte in tree manifest"); 187 memcpy(buf, data + pos, n); 188 buf[n] = '\0'; 189 pos = (end < len) ? end + 1u : end; 190 dist_trim_trail(buf); 191 192 if (first) { 193 first = 0; 194 if (strcmp(buf, DIST_TREE_MAGIC) != 0) 195 return dist_set_err(err, errcap, "bad tree magic/version"); 196 continue; 197 } 198 199 t = dist_trim_lead(buf); 200 if (*t == '\0' || *t == '#') continue; 201 202 if (*t == '[') { 203 if (strcmp(t, "[file]") != 0) 204 return dist_set_err(err, errcap, "unknown tree section"); 205 if ((top_seen & (F_HASH | F_TOP_BLOB)) != (F_HASH | F_TOP_BLOB)) 206 return dist_set_err(err, errcap, "missing required top-level field"); 207 if (sec == TREE_SEC_FILE && 208 finalize_file(out, file_seen, err, errcap) != DIST_OK) 209 return DIST_ERR; 210 if (out->n_entries >= out->cap_entries) 211 return dist_set_err(err, errcap, "too many tree files"); 212 memset(&out->entries[out->n_entries], 0, sizeof out->entries[0]); 213 ++out->n_entries; 214 sec = TREE_SEC_FILE; 215 file_seen = 0; 216 continue; 217 } 218 219 eq = strchr(t, '='); 220 if (!eq) return dist_set_err(err, errcap, "expected key = value"); 221 *eq = '\0'; 222 key = t; 223 dist_trim_trail(key); 224 val = dist_trim_lead(eq + 1); 225 226 if (sec == TREE_SEC_TOP) { 227 if (strcmp(key, "hash") == 0) { 228 if (check_dup(top_seen, F_HASH, err, errcap) != DIST_OK) 229 return DIST_ERR; 230 if (strcmp(val, DIST_TREE_HASH) != 0) 231 return dist_set_err(err, errcap, "unsupported tree hash"); 232 top_seen |= F_HASH; 233 } else if (strcmp(key, "blob") == 0) { 234 if (check_dup(top_seen, F_TOP_BLOB, err, errcap) != DIST_OK) 235 return DIST_ERR; 236 if (strcmp(val, DIST_TREE_BLOB_FORMAT) != 0) 237 return dist_set_err(err, errcap, "unsupported tree blob format"); 238 top_seen |= F_TOP_BLOB; 239 } else { 240 return dist_set_err(err, errcap, "unknown top-level tree key"); 241 } 242 } else { 243 DistTreeEntry* e = &out->entries[out->n_entries - 1u]; 244 if (strcmp(key, "path") == 0) { 245 if (check_dup(file_seen, F_PATH, err, errcap) != DIST_OK) 246 return DIST_ERR; 247 if (!dist_tree_path_valid(val)) 248 return dist_set_err(err, errcap, "unsafe tree path"); 249 if (dist_copy_field(e->path, sizeof e->path, val, err, errcap) != 250 DIST_OK) 251 return DIST_ERR; 252 file_seen |= F_PATH; 253 } else if (strcmp(key, "mode") == 0) { 254 if (check_dup(file_seen, F_MODE, err, errcap) != DIST_OK) 255 return DIST_ERR; 256 if (dist_tree_mode_parse(val, &e->mode) != DIST_OK) 257 return dist_set_err(err, errcap, "bad tree mode"); 258 file_seen |= F_MODE; 259 } else if (strcmp(key, "size") == 0) { 260 if (check_dup(file_seen, F_SIZE, err, errcap) != DIST_OK) 261 return DIST_ERR; 262 if (dist_parse_u64(val, &e->size) != DIST_OK) 263 return dist_set_err(err, errcap, "bad tree size"); 264 file_seen |= F_SIZE; 265 } else if (strcmp(key, "blob") == 0) { 266 if (check_dup(file_seen, F_FILE_BLOB, err, errcap) != DIST_OK) 267 return DIST_ERR; 268 if (hex_hash(val, e->blob) != DIST_OK) 269 return dist_set_err(err, errcap, "bad tree blob hash"); 270 file_seen |= F_FILE_BLOB; 271 } else if (strcmp(key, "root") == 0) { 272 if (check_dup(file_seen, F_ROOT, err, errcap) != DIST_OK) 273 return DIST_ERR; 274 if (hex_hash(val, e->root) != DIST_OK) 275 return dist_set_err(err, errcap, "bad tree blob root"); 276 file_seen |= F_ROOT; 277 } else { 278 return dist_set_err(err, errcap, "unknown [file] tree key"); 279 } 280 } 281 } 282 283 if (first) return dist_set_err(err, errcap, "bad tree magic/version"); 284 if ((top_seen & (F_HASH | F_TOP_BLOB)) != (F_HASH | F_TOP_BLOB)) 285 return dist_set_err(err, errcap, "missing required top-level field"); 286 if (sec == TREE_SEC_FILE && 287 finalize_file(out, file_seen, err, errcap) != DIST_OK) 288 return DIST_ERR; 289 return DIST_OK; 290 } 291 292 void dist_tree_id(uint8_t out[DIST_BLAKE2B_LEN], const uint8_t* manifest, 293 size_t len) { 294 /* Plain BLAKE2b of the canonical tree bytes: this id is the package 295 * format's tree-object hash (verified via pkg_hash), so it must not be 296 * domain-prefixed. See dist_blob_id. */ 297 dist_blake2b(out, manifest, len); 298 } 299 300 const DistTreeEntry* dist_tree_find(const DistTree* tree, const char* path) { 301 size_t i; 302 if (!tree || !path) return NULL; 303 for (i = 0; i < tree->n_entries; ++i) 304 if (strcmp(tree->entries[i].path, path) == 0) return &tree->entries[i]; 305 return NULL; 306 }