solver_greedy: init

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;
+}