From 5602a17e4c916c1fe90a0025fbdceb0621e2e9ba Mon Sep 17 00:00:00 2001 From: sinanmohd Date: Wed, 3 Jul 2024 19:16:21 +0530 Subject: solver_greedy: init --- src/build.c | 4 ++- src/evanix-py.c | 5 +++- src/evanix.c | 5 ++-- src/jobs.c | 2 -- src/meson.build | 1 + src/queue.c | 28 ++++++++++++++++--- src/solver_greedy.c | 77 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 111 insertions(+), 11 deletions(-) create mode 100644 src/solver_greedy.c (limited to 'src') diff --git a/src/build.c b/src/build.c index 30a821a..8952ff5 100644 --- a/src/build.c +++ b/src/build.c @@ -25,7 +25,7 @@ void *build_thread_entry(void *build_thread) goto out; } - if (CIRCLEQ_EMPTY(&bt->queue->jobs)) { + if (queue_isempty(&bt->queue->jobs)) { if (bt->queue->state == Q_ITS_OVER) goto out; else if (bt->queue->state == Q_SEM_WAIT) @@ -51,6 +51,8 @@ static int build(struct queue *queue) char out_link[NAME_MAX] = "result"; ret = queue_pop(queue, &job, queue->htab); + if (ret == -ESRCH) + return EAGAIN; if (ret < 0) return ret; diff --git a/src/evanix-py.c b/src/evanix-py.c index 1ee2ec0..c010e27 100644 --- a/src/evanix-py.c +++ b/src/evanix-py.c @@ -8,4 +8,7 @@ static struct PyModuleDef module = { PyModuleDef_HEAD_INIT, "evanix", NULL, -1, methods, }; -PyMODINIT_FUNC PyInit_evanix(void) { return PyModule_Create(&module); } +PyMODINIT_FUNC PyInit_evanix(void) +{ + return PyModule_Create(&module); +} diff --git a/src/evanix.c b/src/evanix.c index 29b78f3..cd35782 100644 --- a/src/evanix.c +++ b/src/evanix.c @@ -1,6 +1,5 @@ #include #include -#include #include #include "build.h" @@ -15,8 +14,8 @@ static const char usage[] = " -f, --flake Build a flake.\n" " -d, --dry-run Show what derivations would be " "built.\n" - " -s, --system System to build for." - " -m, --max-build Max number of builds." + " -s, --system System to build for.\n" + " -m, --max-build Max number of builds.\n" " -p, --pipelined Use evanix build pipeline.\n" " -c, --close-stderr-exec Close stderr on exec.\n" "\n"; diff --git a/src/jobs.c b/src/jobs.c index aeac2fa..c65de63 100644 --- a/src/jobs.c +++ b/src/jobs.c @@ -370,7 +370,6 @@ static int job_new(struct job **j, char *name, char *drv_path, char *attr, job->scheduled = false; job->stale = false; job->id = -1; - job->age = 0; job->outputs_size = 0; job->outputs_filled = 0; @@ -466,4 +465,3 @@ void job_stale_set(struct job *job) for (size_t i = 0; i < job->parents_filled; i++) job_stale_set(job->parents[i]); } - diff --git a/src/meson.build b/src/meson.build index 7a42999..5e6e2de 100644 --- a/src/meson.build +++ b/src/meson.build @@ -8,6 +8,7 @@ e = executable( 'build.c', 'htab.c', 'solver_util.c', + 'solver_greedy.c', ], include_directories: evanix_inc, diff --git a/src/queue.c b/src/queue.c index 148ca9a..35daf36 100644 --- a/src/queue.c +++ b/src/queue.c @@ -5,7 +5,9 @@ #include #include +#include "evanix.h" #include "queue.h" +#include "solver_greedy.h" #include "util.h" #define MAX_NIX_PKG_COUNT 200000 @@ -51,6 +53,18 @@ static int queue_dag_isolate(struct job *job, struct job *keep_parent, return 0; } +int queue_isempty(struct job_clist *jobs) +{ + struct job *j; + + CIRCLEQ_FOREACH (j, jobs, clist) { + if (j->stale == false) + return false; + } + + return true; +} + /* remove a node along with all it's ancestors recursively */ int queue_ancestors_rm(struct job *job, struct job_clist *jobs, struct htab *htab) @@ -59,7 +73,7 @@ int queue_ancestors_rm(struct job *job, struct job_clist *jobs, int ret; job_stale_set(job); - CIRCLEQ_FOREACH(j, jobs, clist) { + CIRCLEQ_FOREACH (j, jobs, clist) { if (j->stale == false) continue; @@ -107,8 +121,7 @@ void *queue_thread_entry(void *queue_thread) int queue_pop(struct queue *queue, struct job **job, struct htab *htab) { int ret; - - struct job *j = CIRCLEQ_FIRST(&queue->jobs); + struct job *j; if (CIRCLEQ_EMPTY(&queue->jobs)) { print_err("%s", "Empty queue"); @@ -116,6 +129,13 @@ int queue_pop(struct queue *queue, struct job **job, struct htab *htab) } pthread_mutex_lock(&queue->mutex); + if (evanix_opts.max_build) { + ret = solver_greedy(&queue->jobs, &queue->resources, &j); + if (ret < 0) + return ret; + } else { + j = CIRCLEQ_FIRST(&queue->jobs); + } ret = queue_dag_isolate(j, NULL, &queue->jobs, htab); if (ret < 0) return ret; @@ -245,7 +265,7 @@ int queue_thread_new(struct queue_thread **queue_thread, FILE *stream) ret = -errno; goto out_free_qt; } - qt->queue->age = 0; + qt->queue->resources = evanix_opts.max_build; qt->queue->jobid = NULL; qt->queue->state = Q_SEM_WAIT; ret = sem_init(&qt->queue->sem, 0, 0); diff --git a/src/solver_greedy.c b/src/solver_greedy.c new file mode 100644 index 0000000..79472b5 --- /dev/null +++ b/src/solver_greedy.c @@ -0,0 +1,77 @@ +#include +#include + +#include "jobs.h" +#include "queue.h" +#include "solver_greedy.h" +#include "util.h" + +static float conformity(struct job *job); +static int32_t builds_isolated(struct job *job); + +/* conformity is a ratio between number of direct feasible derivations sharing + * dependencies of a derivation and total number of dependencies */ +static float conformity(struct job *job) +{ + float conformity = 0; + + if (job->deps_filled == 0) + return 0; + + for (size_t i = 0; i < job->deps_filled; i++) { + for (size_t j = 0; j < job->deps[i]->parents_filled; j++) { + /* don't count the job itself */ + if (job->deps[i]->parents[j] == job) + continue; + /* don't count stale parents */ + if (job->deps[i]->parents[j]->stale) + continue; + + conformity++; + } + } + conformity /= job->deps_filled; + + return conformity; +} + +static int32_t builds_isolated(struct job *job) +{ + return job->deps_filled + 1; +} + +int solver_greedy(struct job_clist *q, int32_t *max_build, struct job **job) +{ + struct job *j; + float conformity_cur; + + struct job *selected = NULL; + float conformity_max = -1; + + CIRCLEQ_FOREACH (j, q, clist) { + if (j->stale) { + continue; + } else if (builds_isolated(j) > *max_build) { + job_stale_set(j); + continue; + } + } + + CIRCLEQ_FOREACH (j, q, clist) { + if (j->stale) + continue; + + conformity_cur = conformity(j); + if (conformity_cur > conformity_max) { + conformity_max = conformity_cur; + selected = j; + } + } + + if (selected == NULL) + return -ESRCH; + + *max_build -= builds_isolated(selected); + *job = selected; + return 0; +} -- cgit v1.2.3