Re: Fix exponential glob
On Fri, 28 Apr 2017 15:31:34 -0600, "Todd C. Miller" wrote: > Here's a diff that hews a bit more closely to the example code in > https://research.swtch.com/glob Ignore that diff for now, it is not correct. - todd
Re: Fix exponential glob
Here's a diff that hews a bit more closely to the example code in
https://research.swtch.com/glob
- todd
Index: lib/libc/gen/glob.c
===
RCS file: /cvs/src/lib/libc/gen/glob.c,v
retrieving revision 1.46
diff -u -p -u -r1.46 glob.c
--- lib/libc/gen/glob.c 28 Dec 2015 22:08:18 - 1.46
+++ lib/libc/gen/glob.c 28 Apr 2017 21:29:24 -
@@ -126,9 +126,6 @@ typedef char Char;
#defineGLOB_LIMIT_STAT 2048
#defineGLOB_LIMIT_READDIR 16384
-/* Limit of recursion during matching attempts. */
-#define GLOB_LIMIT_RECUR 64
-
struct glob_lim {
size_t glim_malloc;
size_t glim_stat;
@@ -161,7 +158,7 @@ static const Char *
static int globexp1(const Char *, glob_t *, struct glob_lim *);
static int globexp2(const Char *, const Char *, glob_t *,
struct glob_lim *);
-static int match(Char *, Char *, Char *, int);
+static int match(Char *, Char *, Char *);
#ifdef DEBUG
static void qprintf(const char *, Char *);
#endif
@@ -753,7 +750,7 @@ glob3(Char *pathbuf, Char *pathbuf_last,
break;
}
- if (!match(pathend, pattern, restpattern, GLOB_LIMIT_RECUR)) {
+ if (!match(pathend, pattern, restpattern)) {
*pathend = EOS;
continue;
}
@@ -882,17 +879,15 @@ globextend(const Char *path, glob_t *pgl
/*
- * pattern matching function for filenames. Each occurrence of the *
- * pattern causes a recursion level.
+ * pattern matching function for filenames.
*/
static int
-match(Char *name, Char *pat, Char *patend, int recur)
+match(Char *name, Char *pat, Char *patend)
{
int ok, negate_range;
Char c, k;
-
- if (recur-- == 0)
- return(GLOB_NOSPACE);
+ Char *nextName = NULL;
+ Char *nextPat = NULL;
while (pat < patend) {
c = *pat++;
@@ -900,21 +895,18 @@ match(Char *name, Char *pat, Char *paten
case M_ALL:
while (pat < patend && (*pat & M_MASK) == M_ALL)
pat++; /* eat consecutive '*' */
- if (pat == patend)
- return(1);
- do {
- if (match(name, pat, patend, recur))
- return(1);
- } while (*name++ != EOS);
- return(0);
+ /* If no match we will restart at name + 1 */
+ nextPat = pat - 1;
+ nextName = name + 1;
+ continue;
case M_ONE:
if (*name++ == EOS)
- return(0);
- break;
+ break;
+ continue;
case M_SET:
ok = 0;
if ((k = *name++) == EOS)
- return(0);
+ break;
if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
++pat;
while (((c = *pat++) & M_MASK) != M_END) {
@@ -933,15 +925,22 @@ match(Char *name, Char *pat, Char *paten
ok = 1;
}
if (ok == negate_range)
- return(0);
- break;
+ break;
+ continue;
default:
if (*name++ != c)
- return(0);
- break;
+ break;
+ continue;
}
+ /* No match, restart if we hit a '*' in pattern. */
+ if (nextName != NULL && *nextName != EOS) {
+ pat = nextPat;
+ name = nextName;
+ continue;
+ }
+ return(0);
}
- return(*name == EOS);
+ return(1);
}
/* Free allocated data belonging to a glob_t structure. */
Pf interface for FQ-CoDel
This is the last bit required in order to actually be able to
use FQ-CoDel. It might require some polish, but I think there's
nothing exceptionally ugly barring the statistics interface.
fqcodel_stats is constructed to have a few fields "compatible"
with the hfsc_class_stats so that byte and packet counters can
be extracted in the exactly the same way.
The man page will follow.
OK?
diff --git sbin/pfctl/parse.y sbin/pfctl/parse.y
index 4f49b102609..b4cd978f6d3 100644
--- sbin/pfctl/parse.y
+++ sbin/pfctl/parse.y
@@ -304,19 +304,31 @@ struct node_sc {
struct node_queue_bwm1;
u_int d;
struct node_queue_bwm2;
};
+struct node_fq {
+ u_int flows;
+ u_int quantum;
+ u_int target;
+ u_int interval;
+};
+
struct queue_opts {
int marker;
#defineQOM_BWSPEC 0x01
#defineQOM_PARENT 0x02
#defineQOM_DEFAULT 0x04
#defineQOM_QLIMIT 0x08
+#defineQOM_FLOWS 0x10
+#defineQOM_QUANTUM 0x20
+#defineQOM_INTERVAL0x40
+#defineQOM_TARGET 0x80
struct node_sc realtime;
struct node_sc linkshare;
struct node_sc upperlimit;
+ struct node_fq flowqueue;
char*parent;
int flags;
u_intqlimit;
} queue_opts;
@@ -457,11 +469,11 @@ int parseport(char *, struct range *r, int);
%token REASSEMBLE ANCHOR
%token SET OPTIMIZATION TIMEOUT LIMIT LOGINTERFACE BLOCKPOLICY RANDOMID
%token SYNPROXY FINGERPRINTS NOSYNC DEBUG SKIP HOSTID
%token ANTISPOOF FOR INCLUDE MATCHES
%token BITMASK RANDOM SOURCEHASH ROUNDROBIN LEASTSTATES STATICPORT PROBABILITY
-%token WEIGHT BANDWIDTH
+%token WEIGHT BANDWIDTH FLOWS QUANTUM INTERVAL TARGET
%token QUEUE PRIORITY QLIMIT RTABLE RDOMAIN MINIMUM BURST PARENT
%token LOAD RULESET_OPTIMIZATION RTABLE RDOMAIN PRIO ONCE DEFAULT
%token STICKYADDRESS MAXSRCSTATES MAXSRCNODES SOURCETRACK GLOBAL RULE
%token MAXSRCCONN MAXSRCCONNRATE OVERLOAD FLUSH SLOPPY PFLOW
%token TAGGED TAG IFBOUND FLOATING STATEPOLICY STATEDEFAULTS ROUTE
@@ -1317,10 +1329,15 @@ queue_opts_l: queue_opts_l queue_opt
queue_opt : BANDWIDTH scspec optscs {
if (queue_opts.marker & QOM_BWSPEC) {
yyerror("bandwidth cannot be respecified");
YYERROR;
}
+ if (queue_opts.marker & QOM_FLOWS) {
+ yyerror("bandwidth cannot be specified for "
+ "a flow queue");
+ YYERROR;
+ }
queue_opts.marker |= QOM_BWSPEC;
queue_opts.linkshare = $2;
queue_opts.realtime= $3.realtime;
queue_opts.upperlimit = $3.upperlimit;
}
@@ -1336,13 +1353,13 @@ queue_opt : BANDWIDTH scspec optscs
{
if (queue_opts.marker & QOM_DEFAULT) {
yyerror("default cannot be respecified");
YYERROR;
}
queue_opts.marker |= QOM_DEFAULT;
- queue_opts.flags |= HFSC_DEFAULTCLASS;
+ queue_opts.flags |= PFQS_DEFAULT;
}
- | QLIMIT NUMBER {
+ | QLIMIT NUMBER {
if (queue_opts.marker & QOM_QLIMIT) {
yyerror("qlimit cannot be respecified");
YYERROR;
}
if ($2 < 0 || $2 > 65535) {
@@ -1350,10 +1367,83 @@ queue_opt : BANDWIDTH scspec optscs
{
YYERROR;
}
queue_opts.marker |= QOM_QLIMIT;
queue_opts.qlimit = $2;
}
+ | FLOWS NUMBER {
+ if (queue_opts.marker & QOM_FLOWS) {
+ yyerror("number of flows cannot be
respecified");
+ YYERROR;
+ }
+ if (queue_opts.marker & QOM_BWSPEC) {
+ yyerror("bandwidth cannot be specified for "
+ "a flow queue");
+ YYERROR;
+ }
+ if ($2 < 0 || $2 > 32767) {
+ yyerror("number of flows out of range: "
+ "max 32767");
+ YYERROR;
+ }
+
Re: Fix exponential glob
That patch seems to have gotten munged and there was a duplicate
return statement. This one works for me.
- todd
Index: lib/libc/gen/glob.c
===
RCS file: /cvs/src/lib/libc/gen/glob.c,v
retrieving revision 1.46
diff -u -p -u -r1.46 glob.c
--- lib/libc/gen/glob.c 28 Dec 2015 22:08:18 - 1.46
+++ lib/libc/gen/glob.c 28 Apr 2017 16:57:17 -
@@ -126,9 +126,6 @@ typedef char Char;
#defineGLOB_LIMIT_STAT 2048
#defineGLOB_LIMIT_READDIR 16384
-/* Limit of recursion during matching attempts. */
-#define GLOB_LIMIT_RECUR 64
-
struct glob_lim {
size_t glim_malloc;
size_t glim_stat;
@@ -161,7 +158,7 @@ static const Char *
static int globexp1(const Char *, glob_t *, struct glob_lim *);
static int globexp2(const Char *, const Char *, glob_t *,
struct glob_lim *);
-static int match(Char *, Char *, Char *, int);
+static int match(Char *, Char *, Char *);
#ifdef DEBUG
static void qprintf(const char *, Char *);
#endif
@@ -753,7 +750,7 @@ glob3(Char *pathbuf, Char *pathbuf_last,
break;
}
- if (!match(pathend, pattern, restpattern, GLOB_LIMIT_RECUR)) {
+ if (!match(pathend, pattern, restpattern)) {
*pathend = EOS;
continue;
}
@@ -883,17 +880,24 @@ globextend(const Char *path, glob_t *pgl
/*
* pattern matching function for filenames. Each occurrence of the *
- * pattern causes a recursion level.
+ * pattern causes an iteration.
+ *
+ * Note, this function differs from the original as per the discussion
+ * here: https://research.swtch.com/glob
+ *
+ * Basically we removed the recursion and made it use the algorithm
+ * from Russ Cox to not go quadratic on cases like a file called
+ * ("a" x 100) . "x" matched against a pattern like "a*a*a*a*a*a*a*y".
*/
static int
-match(Char *name, Char *pat, Char *patend, int recur)
+match(Char *name, Char *pat, Char *patend)
{
int ok, negate_range;
Char c, k;
+ Char *nextp = NULL;
+ Char *nextn = NULL;
- if (recur-- == 0)
- return(GLOB_NOSPACE);
-
+loop:
while (pat < patend) {
c = *pat++;
switch (c & M_MASK) {
@@ -902,19 +906,19 @@ match(Char *name, Char *pat, Char *paten
pat++; /* eat consecutive '*' */
if (pat == patend)
return(1);
- do {
- if (match(name, pat, patend, recur))
- return(1);
- } while (*name++ != EOS);
- return(0);
+ if (*name == EOS)
+ return(0);
+ nextn = name + 1;
+ nextp = pat - 1;
+ break;
case M_ONE:
if (*name++ == EOS)
- return(0);
+ goto fail;
break;
case M_SET:
ok = 0;
if ((k = *name++) == EOS)
- return(0);
+ goto fail;
if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
++pat;
while (((c = *pat++) & M_MASK) != M_END) {
@@ -933,15 +937,24 @@ match(Char *name, Char *pat, Char *paten
ok = 1;
}
if (ok == negate_range)
- return(0);
+ goto fail;
break;
default:
if (*name++ != c)
- return(0);
+ goto fail;
break;
}
}
- return(*name == EOS);
+ if (*name == EOS)
+ return(1);
+
+fail:
+ if (nextn) {
+ pat = nextp;
+ name = nextn;
+ goto loop;
+ }
+ return(0);
}
/* Free allocated data belonging to a glob_t structure. */
Fix exponential glob
As reported in https://research.swtch.com/glob, matching
aaa with a*a*a*a*a*a*...etc takes exponential time.
Tested with rsc's program: https://news.ycombinator.com/item?id=14187948
I copied the glob implementation from one of the BSDs - I believe
FreeBSD - into a standalone C program and ran that program on the same
Linux system as the rest of the tests. Here's the version that tests the
system glob. If you run it on your FooBSD systems you can see whether it
runs quickly or not. The program assumes that you've already done:
rm -rf /tmp/glob
mkdir /tmp/glob
cd /tmp/glob
touch $(perl -e 'print "a"x100')
And here's the program:
#include
#include
#include
#include
#include
#include
#include
int
main(void)
{
glob_t g;
char pattern[1000], *p;
struct timespec t, t2;
double dt;
int i, j, k;
chdir("/tmp/glob");
setlinebuf(stdout);
int mul = 1000;
for(i = 0; i < 100; i++) {
p = pattern;
for (k = 0; k < i; k++) {
*p++ = 'a';
*p++ = '*';
}
*p++ = 'b';
*p = '\0';
printf("# %d %s\n", i, pattern);
clock_gettime(CLOCK_REALTIME, );
for (j = 0; j < mul; j++) {
memset(, 0, sizeof g);
if(glob(pattern, 0, 0, ) != GLOB_NOMATCH) {
fprintf(stderr, "error: found matches\n");
exit(2);
}
globfree();
}
clock_gettime(CLOCK_REALTIME, );
t2.tv_sec -= t.tv_sec;
t2.tv_nsec -= t.tv_nsec;
dt = t2.tv_sec + (double)t2.tv_nsec/1e9;
printf("%d %.9f\n", i, dt/mul);
fflush(stdout);
if(dt/mul >= 0.0001)
mul = 1;
if(i >= 8 && dt/mul >= 10)
break;
}
}
I won't be filing any specific bugs myself. I mailed oss-security@ this
morning, which should reach relevant BSD maintainers, but more bug
filing can't hurt.
Fix ported from
https://perl5.git.perl.org/perl.git/commit/33252c318625f3c6c89b816ee88481940e3e6f95
diff --git a/lib/libc/gen/glob.c b/lib/libc/gen/glob.c
index e521dcd098d..ee9ab78ef88 100644
--- a/lib/libc/gen/glob.c
+++ b/lib/libc/gen/glob.c
@@ -126,9 +126,6 @@ typedef char Char;
#defineGLOB_LIMIT_STAT2048
#defineGLOB_LIMIT_READDIR16384
-/* Limit of recursion during matching attempts. */
-#define GLOB_LIMIT_RECUR64
-
struct glob_lim {
size_tglim_malloc;
size_tglim_stat;
@@ -161,7 +158,7 @@ static const Char *
static int globexp1(const Char *, glob_t *, struct glob_lim *);
static int globexp2(const Char *, const Char *, glob_t *,
struct glob_lim *);
-static int match(Char *, Char *, Char *, int);
+static int match(Char *, Char *, Char *);
#ifdef DEBUG
static void qprintf(const char *, Char *);
#endif
@@ -753,7 +750,7 @@ glob3(Char *pathbuf, Char *pathbuf_last, Char
*pathend, Char *pathend_last,
break;
}
-if (!match(pathend, pattern, restpattern, GLOB_LIMIT_RECUR)) {
+if (!match(pathend, pattern, restpattern)) {
*pathend = EOS;
continue;
}
@@ -883,17 +880,25 @@ globextend(const Char *path, glob_t *pglob, struct
glob_lim *limitp,
/*
* pattern matching function for filenames. Each occurrence of the *
- * pattern causes a recursion level.
+ * pattern causes an iteration.
+ *
+ * Note, this function differs from the original as per the discussion
+ * here: https://research.swtch.com/glob
+ *
+ * Basically we removed the recursion and made it use the algorithm
+ * from Russ Cox to not go quadratic on cases like a file called ("a" x
100) . "x"
+ * matched against a pattern like "a*a*a*a*a*a*a*y".
+ *
*/
static int
-match(Char *name, Char *pat, Char *patend, int recur)
+match(Char *name, Char *pat, Char *patend)
{
int ok, negate_range;
Char c, k;
+Char *nextp = NULL;
+Char *nextn = NULL;
-if (recur-- == 0)
-return(GLOB_NOSPACE);
-
+loop:
while (pat < patend) {
c = *pat++;
switch (c & M_MASK) {
@@ -902,19 +907,19 @@ match(Char *name, Char *pat, Char *patend, int recur)
pat++;/* eat consecutive '*' */
if (pat == patend)
return(1);
-do {
-if (match(name, pat, patend, recur))
-return(1);
-} while (*name++ != EOS);
-return(0);
+if (*name == EOS)
+return 0;
+nextn = name + 1;
+nextp = pat - 1;
+break;
case M_ONE:
if (*name++ == EOS)
-return(0);
+goto fail;
break;
case M_SET:
ok = 0;
if ((k = *name++) == EOS)
-return(0);
+goto fail;
if ((negate_range =
systat/pftop: PRIO field is gone and is not comming back
OK to remove an unused field?
diff --git usr.bin/systat/pftop.c usr.bin/systat/pftop.c
index 27120174a18..99447b586d7 100644
--- usr.bin/systat/pftop.c
+++ usr.bin/systat/pftop.c
@@ -148,11 +148,10 @@ field_def fields[] = {
{"PEAK", 5, 8, 1, FLD_ALIGN_RIGHT, -1, 0, 0, 0},
{"ANCHOR", 6, 16, 1, FLD_ALIGN_LEFT, -1, 0, 0},
{"QUEUE", 15, 30, 1, FLD_ALIGN_LEFT, -1, 0, 0, 0},
{"BW", 4, 5, 1, FLD_ALIGN_RIGHT, -1, 0, 0, 0},
{"SCH", 3, 4, 1, FLD_ALIGN_LEFT, -1, 0, 0, 0},
- {"PRIO", 1, 4, 1, FLD_ALIGN_RIGHT, -1, 0, 0, 0},
{"DROP_P", 6, 8, 1, FLD_ALIGN_RIGHT, -1, 0, 0, 0},
{"DROP_B", 6, 8, 1, FLD_ALIGN_RIGHT, -1, 0, 0, 0},
{"QLEN", 4, 4, 1, FLD_ALIGN_RIGHT, -1, 0, 0, 0},
{"BORROW", 4, 6, 1, FLD_ALIGN_RIGHT, -1, 0, 0, 0},
{"SUSPENDS", 4, 6, 1, FLD_ALIGN_RIGHT, -1, 0, 0, 0},
@@ -192,18 +191,17 @@ field_def fields[] = {
#define FLD_ANCHOR FIELD_ADDR(fields,24)
/* for queues */
#define FLD_QUEUE FIELD_ADDR(fields,25)
#define FLD_BANDW FIELD_ADDR(fields,26)
#define FLD_SCHED FIELD_ADDR(fields,27)
-#define FLD_PRIOFIELD_ADDR(fields,28)
-#define FLD_DROPP FIELD_ADDR(fields,29)
-#define FLD_DROPB FIELD_ADDR(fields,30)
-#define FLD_QLENFIELD_ADDR(fields,31)
-#define FLD_BORRFIELD_ADDR(fields,32)
-#define FLD_SUSPFIELD_ADDR(fields,33)
-#define FLD_PKTSPS FIELD_ADDR(fields,34)
-#define FLD_BYTESPS FIELD_ADDR(fields,35)
+#define FLD_DROPP FIELD_ADDR(fields,28)
+#define FLD_DROPB FIELD_ADDR(fields,29)
+#define FLD_QLENFIELD_ADDR(fields,30)
+#define FLD_BORRFIELD_ADDR(fields,31)
+#define FLD_SUSPFIELD_ADDR(fields,32)
+#define FLD_PKTSPS FIELD_ADDR(fields,33)
+#define FLD_BYTESPS FIELD_ADDR(fields,34)
/* Define views */
field_def *view0[] = {
FLD_PROTO, FLD_DIR, FLD_SRC, FLD_DEST, FLD_STATE,
FLD_AGE, FLD_EXP, FLD_PKTS, FLD_BYTES, NULL
@@ -245,11 +243,11 @@ field_def *view7[] = {
FLD_PROTO, FLD_DIR, FLD_SRC, FLD_DEST, FLD_SI, FLD_SP, FLD_SA,
FLD_BYTES, FLD_STATE, FLD_PKTS, FLD_AGE, FLD_EXP, FLD_RULE, FLD_GW, NULL
};
field_def *view8[] = {
- FLD_QUEUE, FLD_BANDW, FLD_SCHED, FLD_PRIO, FLD_PKTS, FLD_BYTES,
+ FLD_QUEUE, FLD_BANDW, FLD_SCHED, FLD_PKTS, FLD_BYTES,
FLD_DROPP, FLD_DROPB, FLD_QLEN, FLD_BORR, FLD_SUSP, FLD_PKTSPS,
FLD_BYTESPS, NULL
};
/* Define orderings */
FQ-CoDel: Flow Queue - Controlled Delay
This is an implementation of an FQ-CoDel algorithm that relies
on Pf for configuration and providing flow information via its
stateful inspection.
The purpose of FQ-CoDel is to provide fair sharing of bandwidth
to simultaneous connections (flows in FQ-CoDel terminology) of
different types in presence of a network bottleneck and keeping
the latency low at the same time.
It achieves that by using several algorithms: Modified Deficit
Round Robin++ algorithm services a pre-defined number of flow
queues with a specified quantum of service providing a fair
chance to all queues to send their data. Individual queues are
managed with the CoDel algorithm that controls the time packets
spend in the queue and actively attempts to drop packets that
happen to stay enqueued for too long.
There's a lot that can be said about FQ-CoDel, but I'd like to
point curious readers to these two articles that contain the
best critique in my opinion:
1) http://www.sciencedirect.com/science/article/pii/S1389128615002479
2) https://riteproject.files.wordpress.com/2015/12/p555-grigorescu.pdf
In my personal opinion, this comes in handy when used on the
pppoe router or the like where it provides a much better multi-
user networking experience preventing multiple different
traffic flows from cannibalizing each other.
A few implementation notes:
1) instead of hashing the content of the packet we rely on the
flow id provided by the Pf. First of all OpenBSD queueing
subsystem receives encapsulated layer 2 packets and digging
into the packet for the TCP port number would require massive
and invasive procedures. Regarding the potential for hash
collision attacks since the number of buckets stays the same
and it's a small number, finding a hash collision would be easy
regardless of the used hash function.
2) microuptime is expensive but is not a big deal for APU2-like
hardware even on a 1Gbit link with a 100Mbit bottleneck;
3) we do not perform inverse square root computation in the
runtime but instead provide a pre-computed table of first 399
values for the value of the default interval (100ms). If the
interval value is adjusted, we recompute the whole table for
this instance of fq-codel and scale values up (therefore the
interval cannot be smaller than 100ms).
4) this implementation uses parameters from Linux, which is
also suggested by the RFC draft, but in reality there's not
much difference in behavior compared to FreeBSD for instance.
4) drop during the enqueue is somewhat expensive and Linux guys
have made it much more aggressive. this is something i have a
patch for as well, but it's not included here since it requires
changes to ifq.c.
This is not hooked up to the build yet as it lacks Pf bits and
requires an ifq_free diff from dlg@.
OK?
diff --git sys/net/fq_codel.c sys/net/fq_codel.c
new file mode 100644
index 000..96a7cd3beaa
--- /dev/null
+++ sys/net/fq_codel.c
@@ -0,0 +1,691 @@
+/*
+ * Copyright (c) 2017 Mike Belopuhov
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+/*
+ * Codel - The Controlled-Delay Active Queue Management algorithm
+ * IETF draft-ietf-aqm-codel-07
+ *
+ * Based on the algorithm by Kathleen Nichols and Van Jacobson with
+ * improvements from Dave Taht and Eric Dumazet.
+ */
+
+/*
+ * The FlowQueue-CoDel Packet Scheduler and Active Queue Management
+ * IETF draft-ietf-aqm-fq-codel-06
+ *
+ * Based on the implementation by Rasool Al-Saadi, Centre for Advanced
+ * Internet Architectures, Swinburne University of Technology, Melbourne,
+ * Australia.
+ */
+
+#include
+#include
+#include
+#include
+#include
+
+#include
+#include
+#include
+#include
+
+/* #define FQCODEL_DEBUG 1 */
+
+#ifdef FQCODEL_DEBUG
+#define DPRINTF(x...) printf(x)
+#else
+#define DPRINTF(x...)
+#endif
+
+struct codel {
+ struct mbuf_list q;
+
+ unsigned int dropping:1;/* Dropping state */
+ unsigned int backlog:31;/* Number of bytes in the queue */
+
+ unsigned short drops; /* Free running counter of drops */
+ unsigned short ldrops;/* Value from the previous run */
+
+ struct timeval start; /* The moment queue was above target */
+ struct timeval next; /* Next interval */
+};
+
+struct codel_params {
+ struct
Provide pluggable queueing interface for Pf
By hiding H-FSC behind pfq_ops structure similar to the ifq_ops,
we could provide alternative queueing interfaces for use in Pf.
There are no other functional changes here except that the default
H-FSC qlimit assignment happens in hfsc_class_create so there's no
need to do it in the pf_ioctl code. I did change the order of
elements in hfsc_class_stats a bit to provide some compatibility
between queue stat structures of different traffic conditioners.
This is just to make my life a bit easier.
OK?
diff --git sys/net/hfsc.c sys/net/hfsc.c
index f28b6a5205c..239fd8f36e2 100644
--- sys/net/hfsc.c
+++ sys/net/hfsc.c
@@ -277,10 +277,28 @@ const struct ifq_ops hfsc_ops = {
hfsc_free,
};
const struct ifq_ops * const ifq_hfsc_ops = _ops;
+/*
+ * pf queue glue.
+ */
+
+void *hfsc_pf_alloc(struct ifnet *);
+int hfsc_pf_addqueue(void *, struct pf_queuespec *);
+voidhfsc_pf_free(void *);
+int hfsc_pf_qstats(struct pf_queuespec *, void *, int *);
+
+const struct pfq_ops hfsc_pf_ops = {
+ hfsc_pf_alloc,
+ hfsc_pf_addqueue,
+ hfsc_pf_free,
+ hfsc_pf_qstats
+};
+
+const struct pfq_ops * const pfq_hfsc_ops = _pf_ops;
+
u_int64_t
hfsc_microuptime(void)
{
struct timeval tv;
@@ -321,11 +339,11 @@ hfsc_initialize(void)
IPL_NONE, PR_WAITOK, "hfscclass", NULL);
pool_init(_internal_sc_pl, sizeof(struct hfsc_internal_sc), 0,
IPL_NONE, PR_WAITOK, "hfscintsc", NULL);
}
-struct hfsc_if *
+void *
hfsc_pf_alloc(struct ifnet *ifp)
{
struct hfsc_if *hif;
KASSERT(ifp != NULL);
@@ -340,12 +358,13 @@ hfsc_pf_alloc(struct ifnet *ifp)
return (hif);
}
int
-hfsc_pf_addqueue(struct hfsc_if *hif, struct pf_queuespec *q)
+hfsc_pf_addqueue(void *arg, struct pf_queuespec *q)
{
+ struct hfsc_if *hif = arg;
struct hfsc_class *cl, *parent;
struct hfsc_sc rtsc, lssc, ulsc;
KASSERT(hif != NULL);
@@ -414,12 +433,14 @@ hfsc_pf_qstats(struct pf_queuespec *q, void *ubuf, int
*nbytes)
*nbytes = sizeof(stats);
return (0);
}
void
-hfsc_pf_free(struct hfsc_if *hif)
+hfsc_pf_free(void *arg)
{
+ struct hfsc_if *hif = arg;
+
hfsc_free(0, hif);
}
unsigned int
hfsc_idx(unsigned int nqueues, const struct mbuf *m)
diff --git sys/net/hfsc.h sys/net/hfsc.h
index 88108f60d52..d2e82c807b2 100644
--- sys/net/hfsc.h
+++ sys/net/hfsc.h
@@ -32,13 +32,10 @@
*/
#ifndef _HFSC_H_
#define_HFSC_H_
/* hfsc class flags */
-#defineHFSC_RED0x0001 /* use RED */
-#defineHFSC_ECN0x0002 /* use RED/ECN */
-#defineHFSC_RIO0x0004 /* use RIO */
#defineHFSC_DEFAULTCLASS 0x1000 /* default class */
struct hfsc_pktcntr {
u_int64_t packets;
u_int64_t bytes;
@@ -63,10 +60,17 @@ struct hfsc_sc {
#defineHFSC_LINKSHARINGSC 2
#defineHFSC_UPPERLIMITSC 4
#defineHFSC_DEFAULTSC (HFSC_REALTIMESC|HFSC_LINKSHARINGSC)
struct hfsc_class_stats {
+ struct hfsc_pktcntr xmit_cnt;
+ struct hfsc_pktcntr drop_cnt;
+
+ u_int qlength;
+ u_int qlimit;
+ u_int period;
+
u_int class_id;
u_int32_t class_handle;
struct hfsc_sc rsc;
struct hfsc_sc fsc;
struct hfsc_sc usc;/* upper limit service curve */
@@ -89,16 +93,10 @@ struct hfsc_class_stats {
u_int64_t myfadj; /* cl_myfadj */
u_int64_t vtadj; /* cl_vtadj */
u_int64_t cur_time;
u_int32_t machclk_freq;
- u_int qlength;
- u_int qlimit;
- struct hfsc_pktcntr xmit_cnt;
- struct hfsc_pktcntr drop_cnt;
- u_int period;
-
u_int vtperiod; /* vt period sequence no */
u_int parentperiod; /* parent's vt period seqno */
int nactive;/* number of active children */
/* red and rio related info */
@@ -111,19 +109,15 @@ struct ifnet;
struct ifqueue;
struct pf_queuespec;
struct hfsc_if;
extern const struct ifq_ops * const ifq_hfsc_ops;
+extern const struct pfq_ops * const pfq_hfsc_ops;
#defineHFSC_ENABLED(ifq) ((ifq)->ifq_ops == ifq_hfsc_ops)
#defineHFSC_DEFAULT_QLIMIT 50
-struct hfsc_if *hfsc_pf_alloc(struct ifnet *);
-int hfsc_pf_addqueue(struct hfsc_if *, struct pf_queuespec *);
-voidhfsc_pf_free(struct hfsc_if *);
-int hfsc_pf_qstats(struct pf_queuespec *, void *, int *);
-
voidhfsc_initialize(void);
u_int64_t hfsc_microuptime(void);
#endif /* _KERNEL */
#endif /* _HFSC_H_ */
Re: syslogd error logging during startup
ok
Alexander Bluhm(alexander.bl...@gmx.net) on 2017.04.28 02:17:23 +0200:
> Hi,
>
> jung@ reported that syslogd's error messages are lost if it cannot
> open a logfile. Problem is there is interfering logic during startup
> whether to log to stderr or /dev/console.
>
> My log_setdebug() feature adds too much abstraction, use the global
> variable Started instead. Then all decisions can be done in syslog.c
>
> Set the Started value before the init() function. This means that
> errors during config read will be logged to the console as Initialize
> is still 0. This is better than stderr as this may be redirected
> to /dev/null.
>
> Print the timestamp and hostname also for locally generated messages
> to console, so that they look like all others.
>
> ok?
>
> bluhm
>
> Index: usr.sbin/syslogd/log.c
> ===
> RCS file: /data/mirror/openbsd/cvs/src/usr.sbin/syslogd/log.c,v
> retrieving revision 1.3
> diff -u -p -r1.3 log.c
> --- usr.sbin/syslogd/log.c6 Apr 2017 14:55:43 - 1.3
> +++ usr.sbin/syslogd/log.c27 Apr 2017 13:38:54 -
> @@ -28,7 +28,6 @@
> #include "log.h"
> #include "syslogd.h"
>
> -static intdebug;
> static intverbose;
> static intfacility;
> static const char*log_procname;
> @@ -40,7 +39,6 @@ log_init(int n_debug, int fac)
> {
> extern char *__progname;
>
> - debug = n_debug;
> verbose = n_debug;
> facility = fac;
> log_procinit(__progname);
> @@ -62,18 +60,6 @@ log_procinit(const char *procname)
> }
>
> void
> -log_setdebug(int d)
> -{
> - debug = d;
> -}
> -
> -int
> -log_getdebug(void)
> -{
> - return (debug);
> -}
> -
> -void
> log_setverbose(int v)
> {
> verbose = v;
> @@ -98,18 +84,9 @@ logit(int pri, const char *fmt, ...)
> void
> vlog(int pri, const char *fmt, va_list ap)
> {
> - char ebuf[ERRBUFSIZE];
> - size_t l;
> int saved_errno = errno;
>
> - if (debug) {
> - l = snprintf(ebuf, sizeof(ebuf), "%s: ", log_procname);
> - if (l < sizeof(ebuf))
> - vsnprintf(ebuf+l, sizeof(ebuf)-l, fmt, ap);
> - fprintf(stderr, "%s\n", ebuf);
> - fflush(stderr);
> - } else
> - vlogmsg(facility|pri, log_procname, fmt, ap);
> + vlogmsg(facility|pri, log_procname, fmt, ap);
>
> errno = saved_errno;
> }
> Index: usr.sbin/syslogd/log.h
> ===
> RCS file: /data/mirror/openbsd/cvs/src/usr.sbin/syslogd/log.h,v
> retrieving revision 1.2
> diff -u -p -r1.2 log.h
> --- usr.sbin/syslogd/log.h5 Apr 2017 11:31:45 - 1.2
> +++ usr.sbin/syslogd/log.h27 Apr 2017 13:37:52 -
> @@ -26,8 +26,6 @@
>
> void log_init(int, int);
> void log_procinit(const char *);
> -void log_setdebug(int);
> -int log_getdebug(void);
> void log_setverbose(int);
> int log_getverbose(void);
> void log_warn(const char *, ...)
> Index: usr.sbin/syslogd/syslogd.c
> ===
> RCS file: /data/mirror/openbsd/cvs/src/usr.sbin/syslogd/syslogd.c,v
> retrieving revision 1.243
> diff -u -p -r1.243 syslogd.c
> --- usr.sbin/syslogd/syslogd.c25 Apr 2017 17:45:50 - 1.243
> +++ usr.sbin/syslogd/syslogd.c27 Apr 2017 21:55:10 -
> @@ -204,6 +204,7 @@ int Debug; /* debug flag */
> int Foreground; /* run in foreground, instead of daemonizing */
> char LocalHostName[HOST_NAME_MAX+1]; /* our hostname */
> char *LocalDomain; /* our local domain name */
> +int Started = 0;/* set after privsep */
> int Initialized = 0;/* set when we have initialized ourselves */
>
> int MarkInterval = 20 * 60; /* interval between marks in seconds */
> @@ -465,7 +466,6 @@ main(int argc, char *argv[])
>
> log_init(Debug, LOG_SYSLOG);
> log_procinit("syslogd");
> - log_setdebug(1);
> if (Debug)
> setvbuf(stdout, NULL, _IOLBF, 0);
>
> @@ -731,6 +731,8 @@ main(int argc, char *argv[])
> if (pledge("stdio unix inet recvfd", NULL) == -1)
> err(1, "pledge");
>
> + Started = 1;
> +
> /* Process is now unprivileged and inside a chroot */
> if (Debug)
> event_set_log_callback(logevent);
> @@ -791,8 +793,6 @@ main(int argc, char *argv[])
>
> init();
>
> - log_setdebug(0);
> -
> /* Allocate ctl socket reply buffer if we have a ctl socket */
> if (fd_ctlsock != -1 &&
> (ctl_reply = malloc(CTL_REPLY_MAXSIZE)) == NULL)
> @@ -1627,6 +1627,10 @@ vlogmsg(int pri, const char *proc, const
> l = snprintf(msg, sizeof(msg), "%s[%d]: ", proc, getpid());
> if (l < sizeof(msg))
> vsnprintf(msg + l, sizeof(msg) - l, fmt, ap);
> + if (!Started) {
> + fprintf(stderr, "%s\n", msg);
Re: Include packet timestamp into the mbuf packet header
On Fri, Apr 28, 2017 at 07:54 -0600, Theo de Raadt wrote:
> > One of the prerequisites for FQ_CoDel is ability to track packet
> > enqueue time. To avoid allocating per-packet mbuf tags, I'd prefer
> > to include the timestamp directly into the packet header structure.
> > This can be later used for other purposes as well if need be. OK?
> >
> > diff --git sys/sys/mbuf.h sys/sys/mbuf.h
> > index 202ce8ced8b..daa9facf0dd 100644
> > --- sys/sys/mbuf.h
> > +++ sys/sys/mbuf.h
> > @@ -128,10 +128,11 @@ structpkthdr {
> > u_int16_tcsum_flags;/* checksum flags */
> > u_int16_tether_vtag;/* Ethernet 802.1p+Q vlan tag */
> > u_intph_rtableid; /* routing table id */
> > u_intph_ifidx; /* rcv interface index */
> > u_int8_t ph_loopcnt;/* mbuf is looping in kernel */
> > + struct timeval ph_timestamp; /* packet timestamp */
> > struct pkthdr_pf pf;
> > };
>
> This packs quite poorly into the mbuf. Can you put the timeval ahead
> of ph_loopcnt? That will save a few bytes on some architectures.
Sure,
diff --git sys/sys/mbuf.h sys/sys/mbuf.h
index 202ce8ced8b..72b02e69250 100644
--- sys/sys/mbuf.h
+++ sys/sys/mbuf.h
@@ -127,10 +127,11 @@ structpkthdr {
u_int16_tph_flowid; /* pseudo unique flow id */
u_int16_tcsum_flags;/* checksum flags */
u_int16_tether_vtag;/* Ethernet 802.1p+Q vlan tag */
u_intph_rtableid; /* routing table id */
u_intph_ifidx; /* rcv interface index */
+ struct timeval ph_timestamp; /* packet timestamp */
u_int8_t ph_loopcnt;/* mbuf is looping in kernel */
struct pkthdr_pf pf;
};
/* description of external storage mapped into mbuf, valid if M_EXT set */
Re: Include packet timestamp into the mbuf packet header
> One of the prerequisites for FQ_CoDel is ability to track packet
> enqueue time. To avoid allocating per-packet mbuf tags, I'd prefer
> to include the timestamp directly into the packet header structure.
> This can be later used for other purposes as well if need be. OK?
>
> diff --git sys/sys/mbuf.h sys/sys/mbuf.h
> index 202ce8ced8b..daa9facf0dd 100644
> --- sys/sys/mbuf.h
> +++ sys/sys/mbuf.h
> @@ -128,10 +128,11 @@ struct pkthdr {
> u_int16_tcsum_flags;/* checksum flags */
> u_int16_tether_vtag;/* Ethernet 802.1p+Q vlan tag */
> u_intph_rtableid; /* routing table id */
> u_intph_ifidx; /* rcv interface index */
> u_int8_t ph_loopcnt;/* mbuf is looping in kernel */
> + struct timeval ph_timestamp; /* packet timestamp */
> struct pkthdr_pf pf;
> };
This packs quite poorly into the mbuf. Can you put the timeval ahead
of ph_loopcnt? That will save a few bytes on some architectures.
Include packet timestamp into the mbuf packet header
One of the prerequisites for FQ_CoDel is ability to track packet
enqueue time. To avoid allocating per-packet mbuf tags, I'd prefer
to include the timestamp directly into the packet header structure.
This can be later used for other purposes as well if need be. OK?
diff --git sys/sys/mbuf.h sys/sys/mbuf.h
index 202ce8ced8b..daa9facf0dd 100644
--- sys/sys/mbuf.h
+++ sys/sys/mbuf.h
@@ -128,10 +128,11 @@ structpkthdr {
u_int16_tcsum_flags;/* checksum flags */
u_int16_tether_vtag;/* Ethernet 802.1p+Q vlan tag */
u_intph_rtableid; /* routing table id */
u_intph_ifidx; /* rcv interface index */
u_int8_t ph_loopcnt;/* mbuf is looping in kernel */
+ struct timeval ph_timestamp; /* packet timestamp */
struct pkthdr_pf pf;
};
/* description of external storage mapped into mbuf, valid if M_EXT set */
struct mbuf_ext {
Re: marco's plaintext history patch
On Fri, Apr 28, 2017 at 10:01:06AM +0200, Theo Buehler wrote: > This is an updated version of an old patch by marco [1], including some > improvements and fixes by natano and me. Here's marco's description: > > > I have had enough of corrupt ksh history so I had a look at the code to > > try to fix it. The magical code was very magical so I basically deleted > > most of it and made ksh history into a flat text file. It handles > > multiple ksh instances writing to the same text file with locks just > > like the current ksh does. I haven't noticed any differences in > > behavior running this. > > If you wish to retain your current ksh history, you can create a > plaintext version of it using a command like this (assuming HISTFILE and > HISTSIZE are set): > > cp $HISTFILE $HISTFILE.old > fc -ln 1 | sed 's/^ //' > ~/ksh_hist.txt > > Then apply the patch and install the new ksh. > > Once you've exited all interactive sessions with the old ksh (a reboot is > probably your safest bet), you can use ksh_hist.txt as your history file. > > Note that the old ksh recklessly truncates a history file that it > doesn't understand, so be careful not to run old and new interactive ksh > processes in parallel. > > [1]: https://marc.info/?l=openbsd-tech=131490865525379=2 > In history_load() is there a reason for casting line? + histsave(line_co, (char *)line, 0);
marco's plaintext history patch
This is an updated version of an old patch by marco [1], including some
improvements and fixes by natano and me. Here's marco's description:
> I have had enough of corrupt ksh history so I had a look at the code to
> try to fix it. The magical code was very magical so I basically deleted
> most of it and made ksh history into a flat text file. It handles
> multiple ksh instances writing to the same text file with locks just
> like the current ksh does. I haven't noticed any differences in
> behavior running this.
If you wish to retain your current ksh history, you can create a
plaintext version of it using a command like this (assuming HISTFILE and
HISTSIZE are set):
cp $HISTFILE $HISTFILE.old
fc -ln 1 | sed 's/^ //' > ~/ksh_hist.txt
Then apply the patch and install the new ksh.
Once you've exited all interactive sessions with the old ksh (a reboot is
probably your safest bet), you can use ksh_hist.txt as your history file.
Note that the old ksh recklessly truncates a history file that it
doesn't understand, so be careful not to run old and new interactive ksh
processes in parallel.
[1]: https://marc.info/?l=openbsd-tech=131490865525379=2
Index: alloc.c
===
RCS file: /var/cvs/src/bin/ksh/alloc.c,v
retrieving revision 1.15
diff -u -p -r1.15 alloc.c
--- alloc.c 1 Jun 2016 10:29:20 - 1.15
+++ alloc.c 22 Feb 2017 21:19:37 -
@@ -47,7 +47,7 @@ alloc(size_t size, Area *ap)
if (size > SIZE_MAX - sizeof(struct link))
internal_errorf(1, "unable to allocate memory");
- l = malloc(sizeof(struct link) + size);
+ l = calloc(1, sizeof(struct link) + size);
if (l == NULL)
internal_errorf(1, "unable to allocate memory");
l->next = ap->freelist;
Index: history.c
===
RCS file: /var/cvs/src/bin/ksh/history.c,v
retrieving revision 1.58
diff -u -p -r1.58 history.c
--- history.c 24 Aug 2016 16:09:40 - 1.58
+++ history.c 22 Feb 2017 21:19:37 -
@@ -9,8 +9,7 @@
* a) the original in-memory history mechanism
* b) a more complicated mechanism done by p...@hillside.co.uk
* that more closely follows the real ksh way of doing
- * things. You need to have the mmap system call for this
- * to work on your system
+ * things.
*/
#include
@@ -22,25 +21,16 @@
#include
#include
#include
+#include
#include "sh.h"
#ifdef HISTORY
-# include
-/*
- * variables for handling the data file
- */
-static int histfd;
-static int hsize;
-
-static int hist_count_lines(unsigned char *, int);
-static int hist_shrink(unsigned char *, int);
-static unsigned char *hist_skip_back(unsigned char *,int *,int);
-static void histload(Source *, unsigned char *, int);
-static void histinsert(Source *, int, unsigned char *);
-static void writehistfile(int, char *);
-static int sprinkle(int);
+static voidwritehistfile(void);
+static FILE*history_open(void);
+static int history_load(Source *);
+static voidhistory_close(void);
static int hist_execute(char *);
static int hist_replace(char **, const char *, const char *, int);
@@ -48,11 +38,14 @@ static char **hist_get(const char *, i
static char **hist_get_oldest(void);
static voidhistbackup(void);
+static FILE*histfd;
static char **current; /* current position in history[] */
static char*hname; /* current name of history file */
static int hstarted; /* set after hist_init() called */
static Source *hist_source;
+static uint32_tline_co;
+static struct stat last_sb;
int
c_fc(char **wp)
@@ -546,15 +539,10 @@ sethistfile(const char *name)
/* if the name is the same as the name we have */
if (hname && strcmp(hname, name) == 0)
return;
-
/*
* its a new name - possibly
*/
- if (histfd) {
- /* yes the file is open */
- (void) close(histfd);
- histfd = 0;
- hsize = 0;
+ if (hname) {
afree(hname, APERM);
hname = NULL;
/* let's reset the history */
@@ -562,6 +550,7 @@ sethistfile(const char *name)
hist_source->line = 0;
}
+ history_close();
hist_init(hist_source);
}
@@ -578,6 +567,16 @@ init_histvec(void)
}
}
+static void
+history_lock(int operation)
+{
+ while (flock(fileno(histfd), operation) != 0) {
+ if (errno == EINTR || errno == EAGAIN)
+ continue;
+ else
+ break;
+ }
+}
/*
* Routines added by Peter Collinson BSDI(Europe)/Hillside Systems to
@@ -594,18 +593,28 @@ init_histvec(void)
void
histsave(int lno, const char *cmd, int dowrite)
{
- char
