diff options
| -rw-r--r-- | include/plist/plist.h | 1 | ||||
| -rw-r--r-- | src/bplist.c | 64 | ||||
| -rw-r--r-- | src/jplist.c | 23 | ||||
| -rw-r--r-- | src/oplist.c | 23 | ||||
| -rw-r--r-- | src/out-default.c | 27 | ||||
| -rw-r--r-- | src/out-limd.c | 27 | ||||
| -rw-r--r-- | src/out-plutil.c | 27 | ||||
| -rw-r--r-- | src/plist.h | 13 | ||||
| -rw-r--r-- | src/xplist.c | 26 |
9 files changed, 203 insertions, 28 deletions
diff --git a/include/plist/plist.h b/include/plist/plist.h index 41af8ce..5ea30b8 100644 --- a/include/plist/plist.h +++ b/include/plist/plist.h @@ -144,6 +144,7 @@ extern "C" PLIST_ERR_PARSE = -3, /**< parsing of the input format failed */ PLIST_ERR_NO_MEM = -4, /**< not enough memory to handle the operation */ PLIST_ERR_IO = -5, /**< I/O error */ + PLIST_ERR_CIRCULAR_REF = -6, /**< circular reference detected */ PLIST_ERR_UNKNOWN = -255 /**< an unspecified error occurred */ } plist_err_t; diff --git a/src/bplist.c b/src/bplist.c index b2d0e7c..ca2a556 100644 --- a/src/bplist.c +++ b/src/bplist.c @@ -244,8 +244,10 @@ struct bplist_data { #ifdef DEBUG static int plist_bin_debug = 0; #define PLIST_BIN_ERR(...) if (plist_bin_debug) { fprintf(stderr, "libplist[binparser] ERROR: " __VA_ARGS__); } +#define PLIST_BIN_WRITE_ERR(...) if (plist_bin_debug) { fprintf(stderr, "libplist[binwriter] ERROR: " __VA_ARGS__); } #else #define PLIST_BIN_ERR(...) +#define PLIST_BIN_WRITE_ERR(...) #endif void plist_bin_init(void) @@ -997,35 +999,53 @@ struct serialize_s { ptrarray_t* objects; hashtable_t* ref_table; + hashtable_t* in_stack; }; -static void serialize_plist(node_t node, void* data) +static plist_err_t serialize_plist(node_t node, void* data) { uint64_t *index_val = NULL; struct serialize_s *ser = (struct serialize_s *) data; - uint64_t current_index = ser->objects->len; - //first check that node is not yet in objects + // circular reference check: is node on current recursion stack? + if (hash_table_lookup(ser->in_stack, node)) { + PLIST_BIN_WRITE_ERR("circular reference detected\n"); + return PLIST_ERR_CIRCULAR_REF; + } + + // first check that node is not yet in objects void* val = hash_table_lookup(ser->ref_table, node); - if (val) - { - //data is already in table - return; + if (val) { + // data is already in table + return PLIST_ERR_SUCCESS; } - //insert new ref + + // mark as active + hash_table_insert(ser->in_stack, node, (void*)1); + + // insert new ref index_val = (uint64_t *) malloc(sizeof(uint64_t)); assert(index_val != NULL); - *index_val = current_index; + *index_val = ser->objects->len; hash_table_insert(ser->ref_table, node, index_val); - //now append current node to object array + // now append current node to object array ptr_array_add(ser->objects, node); - //now recurse on children + // now recurse on children node_t ch; + plist_err_t err = PLIST_ERR_SUCCESS; for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) { - serialize_plist(ch, data); + err = serialize_plist(ch, data); + if (err != PLIST_ERR_SUCCESS) { + break; + } } + + // leave recursion stack + hash_table_remove(ser->in_stack, node); + + return err; } #define Log2(x) ((x) == 8 ? 3 : ((x) == 4 ? 2 : ((x) == 2 ? 1 : 0))) @@ -1251,6 +1271,7 @@ plist_err_t plist_to_bin(plist_t plist, char **plist_bin, uint32_t * length) { ptrarray_t* objects = NULL; hashtable_t* ref_table = NULL; + hashtable_t* in_stack = NULL; struct serialize_s ser_s; uint8_t offset_size = 0; uint8_t ref_size = 0; @@ -1280,11 +1301,28 @@ plist_err_t plist_to_bin(plist_t plist, char **plist_bin, uint32_t * length) ptr_array_free(objects); return PLIST_ERR_NO_MEM; } + //hashtable for circular reference detection + in_stack = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL); + if (!in_stack) { + ptr_array_free(objects); + hash_table_destroy(ref_table); + return PLIST_ERR_NO_MEM; + } //serialize plist ser_s.objects = objects; ser_s.ref_table = ref_table; - serialize_plist((node_t)plist, &ser_s); + ser_s.in_stack = in_stack; + plist_err_t err = serialize_plist((node_t)plist, &ser_s); + if (err != PLIST_ERR_SUCCESS) { + ptr_array_free(objects); + hash_table_destroy(ref_table); + hash_table_destroy(in_stack); + return err; + } + //no longer needed + hash_table_destroy(in_stack); + ser_s.in_stack = NULL; //now stream to output buffer offset_size = 0; //unknown yet diff --git a/src/jplist.c b/src/jplist.c index 1c7a932..2e53400 100644 --- a/src/jplist.c +++ b/src/jplist.c @@ -38,6 +38,7 @@ #include "plist.h" #include "strbuf.h" #include "jsmn.h" +#include "hashtable.h" #ifdef DEBUG static int plist_json_debug = 0; @@ -315,18 +316,27 @@ static int num_digits_u(uint64_t i) return n; } -static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify) +static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify, hashtable_t *visited) { plist_data_t data; if (!node) { return PLIST_ERR_INVALID_ARG; } + + if (hash_table_lookup(visited, node)) { + PLIST_JSON_WRITE_ERR("circular reference detected\n"); + return PLIST_ERR_CIRCULAR_REF; + } + + // mark as visited + hash_table_insert(visited, node, (void*)1); + data = plist_get_data(node); if (node->children) { node_t ch; unsigned int n_children = node_n_children(node); for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) { - plist_err_t res = node_estimate_size(ch, size, depth + 1, prettify); + plist_err_t res = _node_estimate_size(ch, size, depth + 1, prettify, visited); if (res < 0) { return res; } @@ -402,6 +412,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept return PLIST_ERR_SUCCESS; } +static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify) +{ + hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL); + if (!visited) return PLIST_ERR_NO_MEM; + plist_err_t err = _node_estimate_size(node, size, depth, prettify, visited); + hash_table_destroy(visited); + return err; +} + plist_err_t plist_to_json(plist_t plist, char **plist_json, uint32_t* length, int prettify) { uint64_t size = 0; diff --git a/src/oplist.c b/src/oplist.c index 277693f..680873c 100644 --- a/src/oplist.c +++ b/src/oplist.c @@ -37,6 +37,7 @@ #include "plist.h" #include "strbuf.h" +#include "hashtable.h" #ifdef DEBUG static int plist_ostep_debug = 0; @@ -359,18 +360,27 @@ static int num_digits_u(uint64_t i) return n; } -static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify) +static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify, hashtable_t *visited) { plist_data_t data; if (!node) { return PLIST_ERR_INVALID_ARG; } + + if (hash_table_lookup(visited, node)) { + PLIST_OSTEP_WRITE_ERR("circular reference detected\n"); + return PLIST_ERR_CIRCULAR_REF; + } + + // mark as visited + hash_table_insert(visited, node, (void*)1); + data = plist_get_data(node); if (node->children) { node_t ch; unsigned int n_children = node_n_children(node); for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) { - plist_err_t res = node_estimate_size(ch, size, depth + 1, prettify); + plist_err_t res = _node_estimate_size(ch, size, depth + 1, prettify, visited); if (res < 0) { return res; } @@ -446,6 +456,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept return PLIST_ERR_SUCCESS; } +static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify) +{ + hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL); + if (!visited) return PLIST_ERR_NO_MEM; + plist_err_t err = _node_estimate_size(node, size, depth, prettify, visited); + hash_table_destroy(visited); + return err; +} + plist_err_t plist_to_openstep(plist_t plist, char **openstep, uint32_t* length, int prettify) { uint64_t size = 0; diff --git a/src/out-default.c b/src/out-default.c index 266070b..09e64c3 100644 --- a/src/out-default.c +++ b/src/out-default.c @@ -38,6 +38,7 @@ #include "plist.h" #include "strbuf.h" #include "time64.h" +#include "hashtable.h" #define MAC_EPOCH 978307200 @@ -310,19 +311,30 @@ static int num_digits_u(uint64_t i) return n; } -static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent, int partial_data) +static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent, int partial_data, hashtable_t *visited) { plist_data_t data; if (!node) { return PLIST_ERR_INVALID_ARG; } + + if (hash_table_lookup(visited, node)) { +#if DEBUG + fprintf(stderr, "libplist: ERROR: circular reference detected\n"); +#endif + return PLIST_ERR_CIRCULAR_REF; + } + + // mark as visited + hash_table_insert(visited, node, (void*)1); + data = plist_get_data(node); if (node->children) { node_t ch; unsigned int n_children = node_n_children(node); for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) { - plist_err_t res = node_estimate_size(ch, size, depth + 1, indent, partial_data); - if (res < 0) { + plist_err_t res = _node_estimate_size(ch, size, depth + 1, indent, partial_data, visited); + if (res != PLIST_ERR_SUCCESS) { return res; } } @@ -401,6 +413,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept return PLIST_ERR_SUCCESS; } +static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent, int partial_data) +{ + hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL); + if (!visited) return PLIST_ERR_NO_MEM; + plist_err_t err = _node_estimate_size(node, size, depth, indent, partial_data, visited); + hash_table_destroy(visited); + return err; +} + static plist_err_t _plist_write_to_strbuf(plist_t plist, strbuf_t *outbuf, plist_write_options_t options) { uint8_t indent = 0; diff --git a/src/out-limd.c b/src/out-limd.c index 7d861f8..e281644 100644 --- a/src/out-limd.c +++ b/src/out-limd.c @@ -40,6 +40,7 @@ #include "strbuf.h" #include "time64.h" #include "base64.h" +#include "hashtable.h" #define MAC_EPOCH 978307200 @@ -278,19 +279,30 @@ static int num_digits_u(uint64_t i) return n; } -static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent) +static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent, hashtable_t *visited) { plist_data_t data; if (!node) { return PLIST_ERR_INVALID_ARG; } + + if (hash_table_lookup(visited, node)) { +#if DEBUG + fprintf(stderr, "libplist: ERROR: circular reference detected\n"); +#endif + return PLIST_ERR_CIRCULAR_REF; + } + + // mark as visited + hash_table_insert(visited, node, (void*)1); + data = plist_get_data(node); if (node->children) { node_t ch; unsigned int n_children = node_n_children(node); for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) { - plist_err_t res = node_estimate_size(ch, size, depth + 1, indent); - if (res < 0) { + plist_err_t res = _node_estimate_size(ch, size, depth + 1, indent, visited); + if (res != PLIST_ERR_SUCCESS) { return res; } } @@ -359,6 +371,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept return PLIST_ERR_SUCCESS; } +static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent) +{ + hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL); + if (!visited) return PLIST_ERR_NO_MEM; + plist_err_t err = _node_estimate_size(node, size, depth, indent, visited); + hash_table_destroy(visited); + return err; +} + static plist_err_t _plist_write_to_strbuf(plist_t plist, strbuf_t *outbuf, plist_write_options_t options) { uint8_t indent = 0; diff --git a/src/out-plutil.c b/src/out-plutil.c index d85f22c..5354aa3 100644 --- a/src/out-plutil.c +++ b/src/out-plutil.c @@ -38,6 +38,7 @@ #include "plist.h" #include "strbuf.h" #include "time64.h" +#include "hashtable.h" #define MAC_EPOCH 978307200 @@ -304,19 +305,30 @@ static int num_digits_u(uint64_t i) return n; } -static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth) +static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, hashtable_t *visited) { plist_data_t data; if (!node) { return PLIST_ERR_INVALID_ARG; } + + if (hash_table_lookup(visited, node)) { +#if DEBUG + fprintf(stderr, "libplist: ERROR: circular reference detected\n"); +#endif + return PLIST_ERR_CIRCULAR_REF; + } + + // mark as visited + hash_table_insert(visited, node, (void*)1); + data = plist_get_data(node); if (node->children) { node_t ch; unsigned int n_children = node_n_children(node); for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) { - plist_err_t res = node_estimate_size(ch, size, depth + 1); - if (res < 0) { + plist_err_t res = _node_estimate_size(ch, size, depth + 1, visited); + if (res != PLIST_ERR_SUCCESS) { return res; } } @@ -388,6 +400,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept return PLIST_ERR_SUCCESS; } +static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth) +{ + hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL); + if (!visited) return PLIST_ERR_NO_MEM; + plist_err_t err = _node_estimate_size(node, size, depth, visited); + hash_table_destroy(visited); + return err; +} + static plist_err_t _plist_write_to_strbuf(plist_t plist, strbuf_t *outbuf, plist_write_options_t options) { plist_err_t res = node_to_string((node_t)plist, &outbuf, 0); diff --git a/src/plist.h b/src/plist.h index a993e3a..3043fb7 100644 --- a/src/plist.h +++ b/src/plist.h @@ -81,4 +81,17 @@ extern plist_err_t plist_write_to_stream_default(plist_t plist, FILE *stream, pl extern plist_err_t plist_write_to_stream_limd(plist_t plist, FILE *stream, plist_write_options_t options); extern plist_err_t plist_write_to_stream_plutil(plist_t plist, FILE *stream, plist_write_options_t options); +static inline unsigned int plist_node_ptr_hash(const void *ptr) +{ + uintptr_t h = (uintptr_t)ptr; + h ^= (h >> 16); + h *= 0x85ebca6b; + return (unsigned int)h; +} + +static inline int plist_node_ptr_compare(const void *a, const void *b) +{ + return a == b; +} + #endif diff --git a/src/xplist.c b/src/xplist.c index dc5213b..c25c6b9 100644 --- a/src/xplist.c +++ b/src/xplist.c @@ -46,6 +46,7 @@ #include "base64.h" #include "strbuf.h" #include "time64.h" +#include "hashtable.h" #define XPLIST_KEY "key" #define XPLIST_KEY_LEN 3 @@ -444,17 +445,29 @@ static int num_digits_u(uint64_t i) return n; } -static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth) +static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, hashtable_t *visited) { plist_data_t data; if (!node) { return PLIST_ERR_INVALID_ARG; } + + if (hash_table_lookup(visited, node)) { + PLIST_XML_WRITE_ERR("circular reference detected\n"); + return PLIST_ERR_CIRCULAR_REF; + } + + // mark as visited + hash_table_insert(visited, node, (void*)1); + data = plist_get_data(node); if (node->children) { node_t ch; for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) { - node_estimate_size(ch, size, depth + 1); + plist_err_t err = _node_estimate_size(ch, size, depth + 1, visited); + if (err != PLIST_ERR_SUCCESS) { + return err; + } } switch (data->type) { case PLIST_DICT: @@ -529,6 +542,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept return PLIST_ERR_SUCCESS; } +static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth) +{ + hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL); + if (!visited) return PLIST_ERR_NO_MEM; + plist_err_t err = _node_estimate_size(node, size, depth, visited); + hash_table_destroy(visited); + return err; +} + plist_err_t plist_to_xml(plist_t plist, char **plist_xml, uint32_t * length) { uint64_t size = 0; |