aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.clang-format1
-rw-r--r--include/evanix.h3
-rw-r--r--include/jobs.h1
-rw-r--r--include/queue.h11
-rw-r--r--include/solver_greedy.h3
-rw-r--r--src/build.c4
-rw-r--r--src/evanix-py.c5
-rw-r--r--src/evanix.c5
-rw-r--r--src/jobs.c2
-rw-r--r--src/meson.build1
-rw-r--r--src/queue.c28
-rw-r--r--src/solver_greedy.c77
12 files changed, 124 insertions, 17 deletions
diff --git a/.clang-format b/.clang-format
index f304ad3..8424e95 100644
--- a/.clang-format
+++ b/.clang-format
@@ -4,6 +4,7 @@ IndentCaseLabels: false
AlignConsecutiveMacros: true
AllowShortIfStatementsOnASingleLine: false
+AllowShortFunctionsOnASingleLine: Empty
ContinuationIndentWidth: 8
IndentWidth: 8
diff --git a/include/evanix.h b/include/evanix.h
index 32f6ed6..48fe110 100644
--- a/include/evanix.h
+++ b/include/evanix.h
@@ -1,4 +1,5 @@
#include <stdbool.h>
+#include <stdint.h>
#ifndef EVANIX_H
@@ -8,7 +9,7 @@ struct evanix_opts_t {
bool ispipelined;
bool close_stderr_exec;
char *system;
- int max_build;
+ uint32_t max_build;
};
extern struct evanix_opts_t evanix_opts;
diff --git a/include/jobs.h b/include/jobs.h
index 41d8adf..ccdff65 100644
--- a/include/jobs.h
+++ b/include/jobs.h
@@ -27,7 +27,6 @@ struct job {
/* solver */
ssize_t id;
- uint64_t age;
bool stale;
};
CIRCLEQ_HEAD(job_clist, job);
diff --git a/include/queue.h b/include/queue.h
index c81f062..cfc67ef 100644
--- a/include/queue.h
+++ b/include/queue.h
@@ -1,7 +1,7 @@
#include <pthread.h>
-#include <stdint.h>
#include <search.h>
#include <semaphore.h>
+#include <stdint.h>
#include <sys/queue.h>
#include "htab.h"
@@ -17,12 +17,14 @@ typedef enum {
struct queue {
struct job_clist jobs;
- struct htab *htab;
- struct jobid *jobid;
sem_t sem;
queue_state_t state;
pthread_mutex_t mutex;
- uint64_t age;
+ struct htab *htab;
+
+ /* solver */
+ struct jobid *jobid;
+ int32_t resources;
};
struct queue_thread {
@@ -35,6 +37,7 @@ 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 htab *htab);
+int queue_isempty(struct job_clist *jobs);
#define QUEUE_H
#endif
diff --git a/include/solver_greedy.h b/include/solver_greedy.h
new file mode 100644
index 0000000..5119818
--- /dev/null
+++ b/include/solver_greedy.h
@@ -0,0 +1,3 @@
+#include "jobs.h"
+
+int solver_greedy(struct job_clist *q, int32_t *max_build, struct job **job);
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 <getopt.h>
#include <stdlib.h>
-#include <stdlib.h>
#include <string.h>
#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 <bool> Use evanix build pipeline.\n"
" -c, --close-stderr-exec <bool> 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 <string.h>
#include <sys/queue.h>
+#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 <errno.h>
+#include <queue.h>
+
+#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;
+}