#include "../core/nsmalloc.h"
#include "../core/hooks.h"
#include "../control/control.h"
+#include "../lib/version.h"
+
+MODULE_VERSION("");
void nsmstats(int hookhum, void *arg);
int nsmhistogram(void *sender, int cargc, char **cargv);
*mean = (double)pool->size / pool->count;
- for (np=pool->first.next;np;np=np->next)
+ for (np=pool->blocks;np;np=np->next)
sumsq+=np->size * np->size;
*stddev = sqrtf((double)sumsq / pool->count - *mean * *mean);
}
/*
- * okay, this is slightly crazy, we create a list of all sizes and sort them.
- * then we make the list contain unique item only, then we calculate frequencies
- * by looking through this sorted list using a binary chop...
- * should be O(n log n)
+ * since this is gonna process over a million allocations, we can't just do
+ * it the simple O(n^2) way, so here's the crazy fast(er) way:
+ * we create a list of all sizes and sort them, then store unique items
+ * we can then calculate frequencies in O(n log n) time by searching this
+ * sorted list using a binary chop...
*/
int nsmhistogram(void *sender, int cargc, char **cargv) {
int i, max;
/* O(n) */
memset(freqs, 0, sizeof(struct nsmhistogram_s) * pool->count);
- for(i=0,np=pool->first.next;np;np=np->next)
+ for(i=0,np=pool->blocks;np;np=np->next)
freqs[i++].size = np->size;
/* O(n log n) */
}
/* outer loop is O(n), inner loop is O(1 + log n) => O(n + n log n) => O(n log n) */
- for(np=pool->first.next;np;np=np->next) {
+ for(np=pool->blocks;np;np=np->next) {
unsigned long low = 0, high = dst;
while(low < high) {
unsigned long mid = (low + high) / 2;
}
if((low > np->size) || (freqs[low].size != np->size)) {
controlreply(sender, "ERROR");
+ free(freqs);
return CMD_ERROR;
} else {
freqs[low].freq++;
/* O(n log n) */
qsort(freqs, dst, sizeof(struct nsmhistogram_s), hcompare_freq);
- max = 20;
+ max = 2000;
- for(i=dst-1;i>=0&&max-->0;i--) {
+ for(i=dst-1;i>=0&&max-->0;i--)
controlreply(sender, "%10lu: %10lu", (unsigned long)freqs[i].size, (unsigned long)freqs[i].freq);
- }
free(freqs);
return CMD_OK;