diff options
| -rw-r--r-- | include/htab.h | 18 | ||||
| -rw-r--r-- | include/jobs.h | 3 | ||||
| -rw-r--r-- | include/queue.h | 5 | ||||
| -rw-r--r-- | src/htab.c | 150 | ||||
| -rw-r--r-- | src/jobs.c | 5 | ||||
| -rw-r--r-- | src/meson.build | 1 | ||||
| -rw-r--r-- | src/queue.c | 141 |
7 files changed, 238 insertions, 85 deletions
diff --git a/include/htab.h b/include/htab.h new file mode 100644 index 0000000..70a0893 --- /dev/null +++ b/include/htab.h @@ -0,0 +1,18 @@ +#include <search.h> + +#ifndef HTAB_H + +struct htab { + struct hsearch_data *table; + char **keys; + size_t keys_size, key_filled; +}; + +void htab_free(struct htab *htab); +int htab_init(struct htab **htab); +int htab_delete(struct htab *htab, const char *key); +int htab_enter(struct htab *htab, const char *key, void *data); +int htab_search(struct htab *htab, char *key, ENTRY **ep); + +#define HTAB_H +#endif diff --git a/include/jobs.h b/include/jobs.h index 623eaea..d4916f7 100644 --- a/include/jobs.h +++ b/include/jobs.h @@ -1,5 +1,5 @@ -#include <stdio.h> #include <stdbool.h> +#include <stdio.h> #include <sys/queue.h> #ifndef JOBS_H @@ -36,6 +36,7 @@ int job_read(FILE *stream, struct job **jobs); int jobs_init(FILE **stream); void job_free(struct job *j); int job_parents_list_insert(struct job *job, struct job *parent); +void job_deps_list_rm(struct job *job, struct job *dep); #define JOBS_H #endif diff --git a/include/queue.h b/include/queue.h index c454339..4aca54b 100644 --- a/include/queue.h +++ b/include/queue.h @@ -3,6 +3,7 @@ #include <semaphore.h> #include <sys/queue.h> +#include "htab.h" #include "jobs.h" #ifndef QUEUE_H @@ -14,7 +15,7 @@ typedef enum { struct queue { struct job_clist jobs; - struct hsearch_data *htab; + struct htab *htab; sem_t sem; queue_state_t state; pthread_mutex_t mutex; @@ -29,7 +30,7 @@ struct queue_thread { int queue_thread_new(struct queue_thread **queue_thread, FILE *stream); void queue_thread_free(struct queue_thread *queue_thread); void *queue_thread_entry(void *queue_thread); -int queue_pop(struct queue *queue, struct job **job, struct hsearch_data *htab); +int queue_pop(struct queue *queue, struct job **job, struct htab *htab); #define QUEUE_H #endif diff --git a/src/htab.c b/src/htab.c new file mode 100644 index 0000000..dde8430 --- /dev/null +++ b/src/htab.c @@ -0,0 +1,150 @@ +/* since hsearch_r does not support deletions dirctly, this is an abstraction on + * top of it with support for deletions, for this to work properly we have to + * strdup the key, this is not a big issue for 100k drv_path strings, it's + * either this or pulling in a external library + */ + +#include <errno.h> +#include <stdlib.h> +#include <string.h> + +#include "htab.h" +#include "util.h" + +#define MAX_NIX_PKG_COUNT 200000 + +static int htab_keys_insert(struct htab *htab, char *key); + +static int htab_keys_insert(struct htab *htab, char *key) +{ + size_t newsize; + void *ret; + + if (htab->key_filled < htab->keys_size) { + htab->keys[htab->key_filled++] = key; + return 0; + } + + newsize = htab->keys_size == 0 ? 1 : htab->keys_size * 2; + ret = realloc(htab->keys, newsize * sizeof(*htab->keys)); + if (ret == NULL) { + print_err("%s", strerror(errno)); + return -errno; + } + + htab->keys = ret; + htab->keys_size = newsize; + htab->keys[htab->key_filled++] = key; + + return 0; +} + +int htab_search(struct htab *htab, char *key, ENTRY **ep) +{ + ENTRY e; + int ret; + + e.key = key; + e.data = NULL; + ret = hsearch_r(e, FIND, ep, htab->table); + if (ret == 0) { + if (errno != ESRCH) { + print_err("%s", strerror(errno)); + return -errno; + } + return ESRCH; + } + + if ((*ep)->data == NULL) { + return ESRCH; + } else { + return 0; + } +} + +int htab_enter(struct htab *htab, const char *key, void *data) +{ + ENTRY e, *ep; + int ret; + + e.key = strdup(key); + if (e.key == NULL) { + print_err("%s", strerror(errno)); + return -errno; + } + + e.data = data; + ret = hsearch_r(e, ENTER, &ep, htab->table); + if (ret == 0) { + print_err("%s", strerror(errno)); + return -errno; + } + ep->data = NULL; + + if (ep->key != e.key) { + free(e.key); + } else { + ret = htab_keys_insert(htab, e.key); + if (ret < 0) + free(e.key); + } + + return ret; +} + +int htab_delete(struct htab *htab, const char *key) +{ + return htab_enter(htab, key, NULL); +} + +int htab_init(struct htab **htab) +{ + int ret; + struct htab *h; + + h = malloc(sizeof(*h)); + if (h == NULL) { + print_err("%s", strerror(errno)); + return -errno; + } + + h->table = calloc(1, sizeof(*h->table)); + if (h == NULL) { + print_err("%s", strerror(errno)); + ret = -errno; + goto out_free_h; + } + + ret = hcreate_r(MAX_NIX_PKG_COUNT, h->table); + if (ret == 0) { + print_err("%s", strerror(errno)); + ret = -errno; + goto out_free_table; + } + ret = 0; + + h->keys = NULL; + h->keys_size = 0; + h->key_filled = 0; + +out_free_table: + if (ret < 0) + free(h->table); +out_free_h: + if (ret < 0) + free(h); + else + *htab = h; + + return ret; +} + +void htab_free(struct htab *htab) +{ + for (size_t i = 0; i < htab->key_filled; i++) + free(htab->keys[i]); + + free(htab->keys); + free(htab->table); + free(htab); +} @@ -16,7 +16,6 @@ static int job_read_inputdrvs(struct job *job, cJSON *input_drvs); static int job_read_outputs(struct job *job, cJSON *outputs); static int job_deps_list_insert(struct job *job, struct job *dep); static int job_output_list_insert(struct job *job, struct output *output); -static void job_deps_list_rm(struct job *job, struct job *dep); static void output_free(struct output *output) { @@ -53,7 +52,7 @@ static int job_output_list_insert(struct job *job, struct output *output) return 0; } -static void job_deps_list_rm(struct job *job, struct job *dep) +void job_deps_list_rm(struct job *job, struct job *dep) { for (size_t i = 0; i < job->deps_filled; i++) { if (job->deps[i] != dep) @@ -370,7 +369,7 @@ int jobs_init(FILE **stream) char *const args[] = { "nix-eval-jobs", "--flake", - "github:sinanmohd/evanix#packages.x86_64-linux", + "github:NixOS/nixpkgs#legacyPackages.x86_64-linux.python310Packages", NULL, }; diff --git a/src/meson.build b/src/meson.build index 41b31da..ea955bc 100644 --- a/src/meson.build +++ b/src/meson.build @@ -6,6 +6,7 @@ e = executable( 'util.c', 'queue.c', 'build.c', + 'htab.c', ], include_directories: evanix_inc, diff --git a/src/queue.c b/src/queue.c index 1fb5ae7..b02474e 100644 --- a/src/queue.c +++ b/src/queue.c @@ -11,8 +11,45 @@ #define MAX_NIX_PKG_COUNT 200000 static int queue_push(struct queue *queue, struct job *job); -static int queue_htab_job_merge(struct job **job, struct hsearch_data *htab); -static int queue_htab_parent_merge(struct job *to, struct job *from); +static int queue_htab_job_merge(struct job **job, struct htab *htab); +static int queue_dag_isolate(struct job *job, struct job *keep_parent, + struct job_clist *jobs, struct htab *htab); + +static int queue_dag_isolate(struct job *job, struct job *keep_parent, + struct job_clist *jobs, struct htab *htab) +{ + int ret; + + for (size_t i = 0; i < job->deps_filled; i++) { + ret = queue_dag_isolate(job->deps[i], job, jobs, htab); + if (ret < 0) + return ret; + } + + for (size_t i = 0; i < job->parents_filled; i++) { + if (job->parents[i] == keep_parent) + continue; + + job_deps_list_rm(job->parents[i], job); + } + + if (keep_parent != NULL) { + job->parents[0] = keep_parent; + job->parents_filled = 1; + } else { + /* it must be tha parent */ + job->parents_filled = 0; + } + + if (!job->transitive) + CIRCLEQ_REMOVE(jobs, job, clist); + + ret = htab_delete(htab, job->drv_path); + if (ret < 0) + return ret; + + return 0; +} void *queue_thread_entry(void *queue_thread) { @@ -41,9 +78,8 @@ void *queue_thread_entry(void *queue_thread) pthread_exit(NULL); } -int queue_pop(struct queue *queue, struct job **job, struct hsearch_data *htab) +int queue_pop(struct queue *queue, struct job **job, struct htab *htab) { - ENTRY e, *ep; int ret; struct job *j = CIRCLEQ_FIRST(&queue->jobs); @@ -54,50 +90,12 @@ int queue_pop(struct queue *queue, struct job **job, struct hsearch_data *htab) } pthread_mutex_lock(&queue->mutex); - - CIRCLEQ_REMOVE(&queue->jobs, j, clist); - if (j->parents_filled <= 0) { - e.key = j->drv_path; - ret = hsearch_r(e, FIND, &ep, htab); - if (ret == 0) { - print_err("%s", strerror(errno)); - } - else - ep->data = NULL; - } - - pthread_mutex_unlock(&queue->mutex); - - *job = j; - return 0; -} - -static int queue_htab_parent_merge(struct job *to, struct job *from) -{ - int ret; - - /* the output from nix-eval-jobs("from") can only have maximum one - * parent */ - for (size_t i = 0; i < to->parents_filled; i++) { - if (strcmp(to->parents[i]->drv_path, - from->parents[0]->drv_path)) - continue; - - /* steal name from "from" */ - if (to->parents[i]->name == NULL) { - to->parents[i]->name = - from->parents[0]->name; - from->parents[0]->name = NULL; - } - - return 0; - } - - ret = job_parents_list_insert(to, from->parents[0]); + ret = queue_dag_isolate(j, NULL, &queue->jobs, htab); if (ret < 0) return ret; - from->parents_filled = 0; + pthread_mutex_unlock(&queue->mutex); + *job = j; return 0; } @@ -107,26 +105,21 @@ static int queue_htab_parent_merge(struct job *to, struct job *from) * - only childrens or dependencies have parent node * - only root node have dependencies */ -static int queue_htab_job_merge(struct job **job, struct hsearch_data *htab) +static int queue_htab_job_merge(struct job **job, struct htab *htab) { struct job *jtab; - ENTRY e, *ep; + ENTRY *ep; int ret; - e.key = (*job)->drv_path; - ret = hsearch_r(e, FIND, &ep, htab); - if (ret == 0) { - if (errno != ESRCH) { - print_err("%s", strerror(errno)); - return -errno; - } - - e.data = *job; - ret = hsearch_r(e, ENTER, &ep, htab); - if (ret == 0) { - print_err("%s", strerror(errno)); - return -errno; - } + // e.key = (*job)->drv_path; + // ret = hsearch_r(e, FIND, &ep, htab); + ret = htab_search(htab, (*job)->drv_path, &ep); + if (ret < 0) { + return ret; + } else if (ret == ESRCH) { + ret = htab_enter(htab, (*job)->drv_path, *job); + if (ret < 0) + return ret; for (size_t i = 0; i < (*job)->deps_filled; i++) { ret = queue_htab_job_merge(&(*job)->deps[i], htab); @@ -148,12 +141,15 @@ static int queue_htab_job_merge(struct job **job, struct hsearch_data *htab) /* only recursive calls with childrens or dependencies can enter this * for a recursive call to happen the parent was just entered into htab - * so, update the parent's deps reference to point to the node in htab + * so, + * - update parent's reference to point to jtab (done by *job = jtab) + * - insert the parent to jtab */ if ((*job)->parents_filled > 0) { - ret = queue_htab_parent_merge(jtab, *job); + ret = job_parents_list_insert(jtab, (*job)->parents[0]); if (ret < 0) return ret; + (*job)->parents_filled = 0; } job_free(*job); @@ -194,8 +190,7 @@ void queue_thread_free(struct queue_thread *queue_thread) CIRCLEQ_FOREACH_FREE(cur, next, &queue_thread->queue->jobs, clist, job_free); - hdestroy_r(queue_thread->queue->htab); - free(queue_thread->queue->htab); + htab_free(queue_thread->queue->htab); ret = sem_destroy(&queue_thread->queue->sem); if (ret < 0) print_err("%s", strerror(errno)); @@ -234,25 +229,13 @@ int queue_thread_new(struct queue_thread **queue_thread, FILE *stream) goto out_free_queue; } - qt->queue->htab = malloc(sizeof(*qt->queue->htab)); - if (qt->queue->htab == NULL) { - print_err("%s", strerror(errno)); - ret = -errno; + ret = htab_init(&qt->queue->htab); + if (ret < 0) goto out_free_sem; - } - ret = hcreate_r(MAX_NIX_PKG_COUNT, qt->queue->htab); - if (ret == 0) { - print_err("%s", strerror(errno)); - ret = -errno; - goto out_free_htab; - } CIRCLEQ_INIT(&qt->queue->jobs); pthread_mutex_init(&qt->queue->mutex, NULL); -out_free_htab: - if (ret < 0) - free(qt->queue->htab); out_free_sem: if (ret < 0) sem_destroy(&qt->queue->sem); |