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