GCOV - Varnish Cache


/*-
 * Copyright (c) 2021 Varnish Software AS
 * All rights reserved.
 *
 * Author: Dridi Boukelmoune <dridi.boukelmoune@gmail.com>
 *
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 */

#include "config.h"

#ifdef ENABLE_WORKSPACE_EMULATOR

#if HAVE_SANITIZER_ASAN_INTERFACE_H
#  include <sanitizer/asan_interface.h>
#endif

#include "cache_varnishd.h"

#include <stdlib.h>

struct ws_alloc {
        unsigned                magic;
#define WS_ALLOC_MAGIC          0x22e7fd05
        unsigned                off;
        unsigned                len;
        char                    *ptr;
        VTAILQ_ENTRY(ws_alloc)  list;
};

VTAILQ_HEAD(ws_alloc_head, ws_alloc);

struct ws_emu {
        unsigned                magic;
#define WS_EMU_MAGIC            0x1c89b6ab
        unsigned                len;
        struct ws               *ws;
        struct ws_alloc_head    head;
};

static const uintptr_t snap_overflowed = (uintptr_t)&snap_overflowed;

static struct ws_emu *
ws_emu(const struct ws *ws)
{
        struct ws_emu *we;

        CAST_OBJ_NOTNULL(we, (void *)ws->s, WS_EMU_MAGIC);
        return (we);
}

void
WS_Assert(const struct ws *ws)
{
        struct ws_emu *we;
        struct ws_alloc *wa, *wa2 = NULL;
        size_t len;

        CHECK_OBJ_NOTNULL(ws, WS_MAGIC);
        assert(ws->s != NULL);
        assert(PAOK(ws->s));
        assert(ws->e != NULL);
        assert(PAOK(ws->e));

        we = ws_emu(ws);
        len = pdiff(ws->s, ws->e);
        assert(len == we->len);

        len = 0;
        VTAILQ_FOREACH(wa, &we->head, list) {
                CHECK_OBJ_NOTNULL(wa, WS_ALLOC_MAGIC);
                wa2 = wa;
                assert(len == wa->off);
                if (wa->ptr == ws->f || wa->ptr == NULL) /* reservation */
                        break;
                AN(wa->len);
                len += PRNDUP(wa->len);
                assert(len <= we->len);
        }

        if (wa != NULL) {
                AZ(VTAILQ_NEXT(wa, list));
                if (wa->ptr == NULL) {
                        AZ(wa->len);
                        assert(ws->f == ws->e);
                        assert(ws->r == ws->e);
                } else {
                        AN(wa->len);
                        assert(ws->f == wa->ptr);
                        assert(ws->r == ws->f + wa->len);
                }
                len += PRNDUP(wa->len);
                assert(len <= we->len);
        } else {
                AZ(ws->f);
                AZ(ws->r);
        }

        DSLb(DBG_WORKSPACE, "WS(%p) = (%s, %p %zu %zu %zu)",
            ws, ws->id, ws->s, wa2 == NULL ? 0 : wa2->off + PRNDUP(wa2->len),
            ws->r == NULL ? 0 : pdiff(ws->f, ws->r),
            pdiff(ws->s, ws->e));
}

int
WS_Allocated(const struct ws *ws, const void *ptr, ssize_t len)
{
        struct ws_emu *we;
        struct ws_alloc *wa;
        uintptr_t p, pa;

        WS_Assert(ws);
        AN(ptr);
        if (len < 0)
                len = strlen(ptr) + 1;
        p = (uintptr_t)ptr;
        we = ws_emu(ws);

        VTAILQ_FOREACH(wa, &we->head, list) {
                pa = (uintptr_t)wa->ptr;
                if (p >= (uintptr_t)ws->f && p <= (uintptr_t)ws->r)
                        return (1);
                /* XXX: clang 12's ubsan triggers a pointer overflow on
                 * the if statement below. Since the purpose is to check
                 * that a pointer+length is within bounds of another
                 * pointer+length it's unclear whether a pointer overflow
                 * is relevant. Worked around for now with uintptr_t.
                 */
                if (p >= pa && p + len <= pa + wa->len)
                        return (1);
        }
        return (0);
}

void
WS_Init(struct ws *ws, const char *id, void *space, unsigned len)
{
        struct ws_emu *we;

        DSLb(DBG_WORKSPACE,
            "WS_Init(%p, \"%s\", %p, %u)", ws, id, space, len);
        assert(space != NULL);
        assert(PAOK(space));
        assert(len >= sizeof *we);

        len = PRNDDN(len - 1);
        INIT_OBJ(ws, WS_MAGIC);
        ws->s = space;
        ws->e = ws->s + len;

        assert(id[0] & 0x20);           // cheesy islower()
        bstrcpy(ws->id, id);

        we = space;
        INIT_OBJ(we, WS_EMU_MAGIC);
        VTAILQ_INIT(&we->head);
        we->len = len;

        WS_Assert(ws);
}

static void
ws_alloc_free(struct ws_emu *we, struct ws_alloc **wap)
{
        struct ws_alloc *wa;

        TAKE_OBJ_NOTNULL(wa, wap, WS_ALLOC_MAGIC);
        AZ(VTAILQ_NEXT(wa, list));
        VTAILQ_REMOVE(&we->head, wa, list);
        free(wa->ptr);
        FREE_OBJ(wa);
}

void
WS_Reset(struct ws *ws, uintptr_t pp)
{
        struct ws_emu *we;
        struct ws_alloc *wa;
        char *p;

        WS_Assert(ws);
        AN(pp);
        if (pp == snap_overflowed) {
                DSLb(DBG_WORKSPACE, "WS_Reset(%p, overflowed)", ws);
                AN(WS_Overflowed(ws));
                return;
        }
        p = (char *)pp;
        DSLb(DBG_WORKSPACE, "WS_Reset(%p, %p)", ws, p);
        AZ(ws->r);

        we = ws_emu(ws);
        while ((wa = VTAILQ_LAST(&we->head, ws_alloc_head)) != NULL &&
            wa->ptr != p)
                ws_alloc_free(we, &wa);
        if (wa == NULL)
                assert(p == ws->s);

        WS_Assert(ws);
}

unsigned
WS_ReqPipeline(struct ws *ws, const void *b, const void *e)
{
        struct ws_emu *we;
        struct ws_alloc *wa;
        unsigned l;

        WS_Assert(ws);
        AZ(ws->f);
        AZ(ws->r);

        if (strcasecmp(ws->id, "req"))
                AZ(b);

        if (b == NULL) {
                AZ(e);
                if (!strcasecmp(ws->id, "req"))
                        WS_Rollback(ws, 0);
                (void)WS_ReserveAll(ws);
                return (0);
        }

        we = ws_emu(ws);
        ALLOC_OBJ(wa, WS_ALLOC_MAGIC);
        AN(wa);
        wa->len = we->len;
        wa->ptr = malloc(wa->len);
        AN(wa->ptr);

        AN(e);
        l = pdiff(b, e);
        assert(l <= wa->len);
        memcpy(wa->ptr, b, l);

        WS_Rollback(ws, 0);
        ws->f = wa->ptr;
        ws->r = ws->f + wa->len;
        VTAILQ_INSERT_TAIL(&we->head, wa, list);
        WS_Assert(ws);
        return (l);
}

static struct ws_alloc *
ws_emu_alloc(struct ws *ws, unsigned len)
{
        struct ws_emu *we;
        struct ws_alloc *wa;
        size_t off = 0;

        WS_Assert(ws);
        AZ(ws->r);

        we = ws_emu(ws);
        wa = VTAILQ_LAST(&we->head, ws_alloc_head);
        CHECK_OBJ_ORNULL(wa, WS_ALLOC_MAGIC);

        if (wa != NULL)
                off = wa->off + PRNDUP(wa->len);
        if (off + len > we->len) {
                WS_MarkOverflow(ws);
                return (NULL);
        }
        if (len == 0)
                len = we->len - off;

        ALLOC_OBJ(wa, WS_ALLOC_MAGIC);
        AN(wa);
        wa->off = off;
        wa->len = len;
        if (len > 0) {
                wa->ptr = malloc(len);
                AN(wa->ptr);
        }
        VTAILQ_INSERT_TAIL(&we->head, wa, list);
        return (wa);
}

void *
WS_Alloc(struct ws *ws, unsigned bytes)
{
        struct ws_alloc *wa;

        assert(bytes > 0);
        wa = ws_emu_alloc(ws, bytes);
        WS_Assert(ws);
        if (wa != NULL) {
                AN(wa->ptr);
                DSLb(DBG_WORKSPACE, "WS_Alloc(%p, %u) = %p",
                    ws, bytes, wa->ptr);
                return (wa->ptr);
        }
        return (NULL);
}

void *
WS_Copy(struct ws *ws, const void *str, int len)
{
        struct ws_alloc *wa;

        AN(str);
        if (len == -1)
                len = strlen(str) + 1;
        assert(len > 0);
        wa = ws_emu_alloc(ws, len);
        WS_Assert(ws);
        if (wa != NULL) {
                AN(wa->ptr);
                memcpy(wa->ptr, str, len);
                DSLb(DBG_WORKSPACE, "WS_Copy(%p, %d) = %p",
                    ws, len, wa->ptr);
                return (wa->ptr);
        }
        return (NULL);
}

uintptr_t
WS_Snapshot(struct ws *ws)
{
        struct ws_emu *we;
        struct ws_alloc *wa;
        void *p;

        WS_Assert(ws);
        assert(ws->r == NULL);
        if (WS_Overflowed(ws)) {
                DSLb(DBG_WORKSPACE, "WS_Snapshot(%p) = overflowed", ws);
                return (snap_overflowed);
        }

        we = ws_emu(ws);
        wa = VTAILQ_LAST(&we->head, ws_alloc_head);
        CHECK_OBJ_ORNULL(wa, WS_ALLOC_MAGIC);
        p = (wa == NULL ? ws->s : wa->ptr);
        DSLb(DBG_WORKSPACE, "WS_Snapshot(%p) = %p", ws, p);
        return ((uintptr_t)p);
}

unsigned
WS_ReserveAll(struct ws *ws)
{
        struct ws_alloc *wa;
        unsigned b;

        wa = ws_emu_alloc(ws, 0);
        AN(wa);

        if (wa->ptr != NULL) {
                AN(wa->len);
                ws->f = wa->ptr;
                ws->r = ws->f + wa->len;
        } else {
                ws->f = ws->r = ws->e;
        }

        b = pdiff(ws->f, ws->r);
        DSLb(DBG_WORKSPACE, "WS_ReserveAll(%p) = %u", ws, b);
        WS_Assert(ws);
        return (b);
}

unsigned
WS_ReserveSize(struct ws *ws, unsigned bytes)
{
        struct ws_emu *we;
        struct ws_alloc *wa;

        assert(bytes > 0);
        wa = ws_emu_alloc(ws, bytes);
        if (wa == NULL)
                return (0);

        AN(wa->ptr);
        assert(wa->len == bytes);
        ws->f = wa->ptr;
        ws->r = ws->f + bytes;
        we = ws_emu(ws);
        DSLb(DBG_WORKSPACE, "WS_ReserveSize(%p, %u/%u) = %u",
            ws, bytes, we->len - wa->off, bytes);
        WS_Assert(ws);
        return (bytes);
}

static void
ws_release(struct ws *ws, unsigned bytes)
{
        struct ws_emu *we;
        struct ws_alloc *wa;

        WS_Assert(ws);
        AN(ws->f);
        AN(ws->r);
        we = ws_emu(ws);
        wa = VTAILQ_LAST(&we->head, ws_alloc_head);
        AN(wa);
        assert(bytes <= wa->len);
        ws->f = ws->r = NULL;

        if (bytes == 0) {
                ws_alloc_free(we, &wa);
                return;
        }

        AN(wa->ptr);
#ifdef ASAN_POISON_MEMORY_REGION
        ASAN_POISON_MEMORY_REGION(wa->ptr + bytes, wa->len - bytes);
#endif
        wa->len = bytes;
        WS_Assert(ws);
}

void
WS_Release(struct ws *ws, unsigned bytes)
{

        ws_release(ws, bytes);
        DSLb(DBG_WORKSPACE, "WS_Release(%p, %u)", ws, bytes);
}

void
WS_ReleaseP(struct ws *ws, const char *ptr)
{
        unsigned l;

        WS_Assert(ws);
        assert(ws->r != NULL);
        assert(ptr >= ws->f);
        assert(ptr <= ws->r);
        l = pdiff(ws->f, ptr);
        ws_release(ws, l);
        DSLb(DBG_WORKSPACE, "WS_ReleaseP(%p, %p (%u))", ws, ptr, l);
}

void *
WS_AtOffset(const struct ws *ws, unsigned off, unsigned len)
{
        struct ws_emu *we;
        struct ws_alloc *wa;

        WS_Assert(ws);
        we = ws_emu(ws);

        VTAILQ_FOREACH(wa, &we->head, list) {
                if (wa->off == off) {
                        assert(wa->len >= len);
                        return (wa->ptr);
                }
        }

        WRONG("invalid offset");
        NEEDLESS(return (NULL));
}

unsigned
WS_ReservationOffset(const struct ws *ws)
{
        struct ws_emu *we;
        struct ws_alloc *wa;

        WS_Assert(ws);
        AN(ws->f);
        AN(ws->r);
        we = ws_emu(ws);
        wa = VTAILQ_LAST(&we->head, ws_alloc_head);
        AN(wa);
        return (wa->off);
}

unsigned
WS_Dump(const struct ws *ws, char where, size_t off, void *buf, size_t len)
{
        struct ws_emu *we;
        struct ws_alloc *wa;
        unsigned l;
        char *b;

        WS_Assert(ws);
        AN(buf);
        AN(len);

        if (strchr("sfr", where) == NULL) {
                errno = EINVAL;
                return (0);
        }

        if (where == 'r' && ws->r == NULL) {
                errno = EAGAIN;
                return (0);
        }

        we = ws_emu(ws);
        wa = VTAILQ_LAST(&we->head, ws_alloc_head);

        l = we->len;
        if (where != 's' && wa != NULL) {
                l -= wa->off;
                if (where == 'f')
                        l -= wa->len;
        }

        if (off > l) {
                errno = EFAULT;
                return (0);
        }

        b = buf;
        if (where == 'f' && ws->r != NULL) {
                if (l > len)
                        l = len;
                AN(wa);
                memcpy(b, wa->ptr, l);
                b += l;
                len -= l;
        }

        if (where == 's') {
                VTAILQ_FOREACH(wa, &we->head, list) {
                        if (len == 0)
                                break;
                        if (wa->ptr == NULL)
                                break;
                        l = vmin_t(size_t, wa->len, len);
                        memcpy(b, wa->ptr, l);
                        b += l;
                        len -= l;
                }
        }

        if (len > 0)
                memset(b, 0xa5, len);
        return (l);
}

static void
ws_emu_panic(struct vsb *vsb, const struct ws *ws)
{
        const struct ws_emu *we;
        const struct ws_alloc *wa;

        we = (void *)ws->s;
        if (PAN_dump_once(vsb, we, WS_EMU_MAGIC, "ws_emu"))
                return;
        VSB_printf(vsb, "len = %u,\n", we->len);

        VTAILQ_FOREACH(wa, &we->head, list) {
                if (PAN_dump_once_oneline(vsb, wa, WS_ALLOC_MAGIC, "ws_alloc"))
                        break;
                VSB_printf(vsb, "off, len, ptr} = {%u, %u, %p}\n",
                    wa->off, wa->len, wa->ptr);
        }

        VSB_indent(vsb, -2);
        VSB_cat(vsb, "},\n");
}

void
WS_Panic(struct vsb *vsb, const struct ws *ws)
{

        if (PAN_dump_struct(vsb, ws, WS_MAGIC, "ws"))
                return;
        if (ws->id[0] != '\0' && (!(ws->id[0] & 0x20))) // cheesy islower()
                VSB_cat(vsb, "OVERFLOWED ");
        VSB_printf(vsb, "id = \"%s\",\n", ws->id);
        VSB_printf(vsb, "{s, e} = {%p", ws->s);
        if (ws->e >= ws->s)
                VSB_printf(vsb, ", +%ld", (long) (ws->e - ws->s));
        else
                VSB_printf(vsb, ", %p", ws->e);
        VSB_cat(vsb, "},\n");
        VSB_printf(vsb, "{f, r} = {%p", ws->f);
        if (ws->r >= ws->f)
                VSB_printf(vsb, ", +%ld", (long) (ws->r - ws->f));
        else
                VSB_printf(vsb, ", %p", ws->r);
        VSB_cat(vsb, "},\n");

        ws_emu_panic(vsb, ws);

        VSB_indent(vsb, -2);
        VSB_cat(vsb, "},\n");
}

#endif /* ENABLE_WORKSPACE_EMULATOR */

		varnish-cache/bin/varnishd/cache/cache_ws_emu.c
0		/*-
1		* Copyright (c) 2021 Varnish Software AS
2		* All rights reserved.
3		*
4		* Author: Dridi Boukelmoune <dridi.boukelmoune@gmail.com>
5		*
6		* SPDX-License-Identifier: BSD-2-Clause
7		*
8		* Redistribution and use in source and binary forms, with or without
9		* modification, are permitted provided that the following conditions
10		* are met:
11		* 1. Redistributions of source code must retain the above copyright
12		* notice, this list of conditions and the following disclaimer.
13		* 2. Redistributions in binary form must reproduce the above copyright
14		* notice, this list of conditions and the following disclaimer in the
15		* documentation and/or other materials provided with the distribution.
16		*
17		* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18		* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19		* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20		* ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
21		* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22		* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23		* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24		* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25		* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26		* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27		* SUCH DAMAGE.
28		*
29		*/
30
31		#include "config.h"
32
33		#ifdef ENABLE_WORKSPACE_EMULATOR
34
35		#if HAVE_SANITIZER_ASAN_INTERFACE_H
36		# include <sanitizer/asan_interface.h>
37		#endif
38
39		#include "cache_varnishd.h"
40
41		#include <stdlib.h>
42
43		struct ws_alloc {
44		unsigned magic;
45		#define WS_ALLOC_MAGIC 0x22e7fd05
46		unsigned off;
47		unsigned len;
48		char *ptr;
49		VTAILQ_ENTRY(ws_alloc) list;
50		};
51
52		VTAILQ_HEAD(ws_alloc_head, ws_alloc);
53
54		struct ws_emu {
55		unsigned magic;
56		#define WS_EMU_MAGIC 0x1c89b6ab
57		unsigned len;
58		struct ws *ws;
59		struct ws_alloc_head head;
60		};
61
62		static const uintptr_t snap_overflowed = (uintptr_t)&snap_overflowed;
63
64		static struct ws_emu *
65	0	ws_emu(const struct ws *ws)
66		{
67		struct ws_emu *we;
68
69	0	CAST_OBJ_NOTNULL(we, (void *)ws->s, WS_EMU_MAGIC);
70	0	return (we);
71		}
72
73		void
74	0	WS_Assert(const struct ws *ws)
75		{
76		struct ws_emu *we;
77	0	struct ws_alloc wa, wa2 = NULL;
78		size_t len;
79
80	0	CHECK_OBJ_NOTNULL(ws, WS_MAGIC);
81	0	assert(ws->s != NULL);
82	0	assert(PAOK(ws->s));
83	0	assert(ws->e != NULL);
84	0	assert(PAOK(ws->e));
85
86	0	we = ws_emu(ws);
87	0	len = pdiff(ws->s, ws->e);
88	0	assert(len == we->len);
89
90	0	len = 0;
91	0	VTAILQ_FOREACH(wa, &we->head, list) {
92	0	CHECK_OBJ_NOTNULL(wa, WS_ALLOC_MAGIC);
93	0	wa2 = wa;
94	0	assert(len == wa->off);
95	0	if (wa->ptr == ws->f \|\| wa->ptr == NULL) /* reservation */
96	0	break;
97	0	AN(wa->len);
98	0	len += PRNDUP(wa->len);
99	0	assert(len <= we->len);
100	0	}
101
102	0	if (wa != NULL) {
103	0	AZ(VTAILQ_NEXT(wa, list));
104	0	if (wa->ptr == NULL) {
105	0	AZ(wa->len);
106	0	assert(ws->f == ws->e);
107	0	assert(ws->r == ws->e);
108	0	} else {
109	0	AN(wa->len);
110	0	assert(ws->f == wa->ptr);
111	0	assert(ws->r == ws->f + wa->len);
112		}
113	0	len += PRNDUP(wa->len);
114	0	assert(len <= we->len);
115	0	} else {
116	0	AZ(ws->f);
117	0	AZ(ws->r);
118		}
119
120	0	DSLb(DBG_WORKSPACE, "WS(%p) = (%s, %p %zu %zu %zu)",
121		ws, ws->id, ws->s, wa2 == NULL ? 0 : wa2->off + PRNDUP(wa2->len),
122		ws->r == NULL ? 0 : pdiff(ws->f, ws->r),
123		pdiff(ws->s, ws->e));
124	0	}
125
126		int
127	0	WS_Allocated(const struct ws ws, const void ptr, ssize_t len)
128		{
129		struct ws_emu *we;
130		struct ws_alloc *wa;
131		uintptr_t p, pa;
132
133	0	WS_Assert(ws);
134	0	AN(ptr);
135	0	if (len < 0)
136	0	len = strlen(ptr) + 1;
137	0	p = (uintptr_t)ptr;
138	0	we = ws_emu(ws);
139
140	0	VTAILQ_FOREACH(wa, &we->head, list) {
141	0	pa = (uintptr_t)wa->ptr;
142	0	if (p >= (uintptr_t)ws->f && p <= (uintptr_t)ws->r)
143	0	return (1);
144		/* XXX: clang 12's ubsan triggers a pointer overflow on
145		* the if statement below. Since the purpose is to check
146		* that a pointer+length is within bounds of another
147		* pointer+length it's unclear whether a pointer overflow
148		* is relevant. Worked around for now with uintptr_t.
149		*/
150	0	if (p >= pa && p + len <= pa + wa->len)
151	0	return (1);
152	0	}
153	0	return (0);
154	0	}
155
156		void
157	0	WS_Init(struct ws ws, const char id, void *space, unsigned len)
158		{
159		struct ws_emu *we;
160
161	0	DSLb(DBG_WORKSPACE,
162		"WS_Init(%p, \"%s\", %p, %u)", ws, id, space, len);
163	0	assert(space != NULL);
164	0	assert(PAOK(space));
165	0	assert(len >= sizeof *we);
166
167	0	len = PRNDDN(len - 1);
168	0	INIT_OBJ(ws, WS_MAGIC);
169	0	ws->s = space;
170	0	ws->e = ws->s + len;
171
172	0	assert(id[0] & 0x20); // cheesy islower()
173	0	bstrcpy(ws->id, id);
174
175	0	we = space;
176	0	INIT_OBJ(we, WS_EMU_MAGIC);
177	0	VTAILQ_INIT(&we->head);
178	0	we->len = len;
179
180	0	WS_Assert(ws);
181	0	}
182
183		static void
184	0	ws_alloc_free(struct ws_emu we, struct ws_alloc *wap)
185		{
186		struct ws_alloc *wa;
187
188	0	TAKE_OBJ_NOTNULL(wa, wap, WS_ALLOC_MAGIC);
189	0	AZ(VTAILQ_NEXT(wa, list));
190	0	VTAILQ_REMOVE(&we->head, wa, list);
191	0	free(wa->ptr);
192	0	FREE_OBJ(wa);
193	0	}
194
195		void
196	0	WS_Reset(struct ws *ws, uintptr_t pp)
197		{
198		struct ws_emu *we;
199		struct ws_alloc *wa;
200		char *p;
201
202	0	WS_Assert(ws);
203	0	AN(pp);
204	0	if (pp == snap_overflowed) {
205	0	DSLb(DBG_WORKSPACE, "WS_Reset(%p, overflowed)", ws);
206	0	AN(WS_Overflowed(ws));
207	0	return;
208		}
209	0	p = (char *)pp;
210	0	DSLb(DBG_WORKSPACE, "WS_Reset(%p, %p)", ws, p);
211	0	AZ(ws->r);
212
213	0	we = ws_emu(ws);
214	0	while ((wa = VTAILQ_LAST(&we->head, ws_alloc_head)) != NULL &&
215	0	wa->ptr != p)
216	0	ws_alloc_free(we, &wa);
217	0	if (wa == NULL)
218	0	assert(p == ws->s);
219
220	0	WS_Assert(ws);
221	0	}
222
223		unsigned
224	0	WS_ReqPipeline(struct ws ws, const void b, const void *e)
225		{
226		struct ws_emu *we;
227		struct ws_alloc *wa;
228		unsigned l;
229
230	0	WS_Assert(ws);
231	0	AZ(ws->f);
232	0	AZ(ws->r);
233
234	0	if (strcasecmp(ws->id, "req"))
235	0	AZ(b);
236
237	0	if (b == NULL) {
238	0	AZ(e);
239	0	if (!strcasecmp(ws->id, "req"))
240	0	WS_Rollback(ws, 0);
241	0	(void)WS_ReserveAll(ws);
242	0	return (0);
243		}
244
245	0	we = ws_emu(ws);
246	0	ALLOC_OBJ(wa, WS_ALLOC_MAGIC);
247	0	AN(wa);
248	0	wa->len = we->len;
249	0	wa->ptr = malloc(wa->len);
250	0	AN(wa->ptr);
251
252	0	AN(e);
253	0	l = pdiff(b, e);
254	0	assert(l <= wa->len);
255	0	memcpy(wa->ptr, b, l);
256
257	0	WS_Rollback(ws, 0);
258	0	ws->f = wa->ptr;
259	0	ws->r = ws->f + wa->len;
260	0	VTAILQ_INSERT_TAIL(&we->head, wa, list);
261	0	WS_Assert(ws);
262	0	return (l);
263	0	}
264
265		static struct ws_alloc *
266	0	ws_emu_alloc(struct ws *ws, unsigned len)
267		{
268		struct ws_emu *we;
269		struct ws_alloc *wa;
270	0	size_t off = 0;
271
272	0	WS_Assert(ws);
273	0	AZ(ws->r);
274
275	0	we = ws_emu(ws);
276	0	wa = VTAILQ_LAST(&we->head, ws_alloc_head);
277	0	CHECK_OBJ_ORNULL(wa, WS_ALLOC_MAGIC);
278
279	0	if (wa != NULL)
280	0	off = wa->off + PRNDUP(wa->len);
281	0	if (off + len > we->len) {
282	0	WS_MarkOverflow(ws);
283	0	return (NULL);
284		}
285	0	if (len == 0)
286	0	len = we->len - off;
287
288	0	ALLOC_OBJ(wa, WS_ALLOC_MAGIC);
289	0	AN(wa);
290	0	wa->off = off;
291	0	wa->len = len;
292	0	if (len > 0) {
293	0	wa->ptr = malloc(len);
294	0	AN(wa->ptr);
295	0	}
296	0	VTAILQ_INSERT_TAIL(&we->head, wa, list);
297	0	return (wa);
298	0	}
299
300		void *
301	0	WS_Alloc(struct ws *ws, unsigned bytes)
302		{
303		struct ws_alloc *wa;
304
305	0	assert(bytes > 0);
306	0	wa = ws_emu_alloc(ws, bytes);
307	0	WS_Assert(ws);
308	0	if (wa != NULL) {
309	0	AN(wa->ptr);
310	0	DSLb(DBG_WORKSPACE, "WS_Alloc(%p, %u) = %p",
311		ws, bytes, wa->ptr);
312	0	return (wa->ptr);
313		}
314	0	return (NULL);
315	0	}
316
317		void *
318	0	WS_Copy(struct ws ws, const void str, int len)
319		{
320		struct ws_alloc *wa;
321
322	0	AN(str);
323	0	if (len == -1)
324	0	len = strlen(str) + 1;
325	0	assert(len > 0);
326	0	wa = ws_emu_alloc(ws, len);
327	0	WS_Assert(ws);
328	0	if (wa != NULL) {
329	0	AN(wa->ptr);
330	0	memcpy(wa->ptr, str, len);
331	0	DSLb(DBG_WORKSPACE, "WS_Copy(%p, %d) = %p",
332		ws, len, wa->ptr);
333	0	return (wa->ptr);
334		}
335	0	return (NULL);
336	0	}
337
338		uintptr_t
339	0	WS_Snapshot(struct ws *ws)
340		{
341		struct ws_emu *we;
342		struct ws_alloc *wa;
343		void *p;
344
345	0	WS_Assert(ws);
346	0	assert(ws->r == NULL);
347	0	if (WS_Overflowed(ws)) {
348	0	DSLb(DBG_WORKSPACE, "WS_Snapshot(%p) = overflowed", ws);
349	0	return (snap_overflowed);
350		}
351
352	0	we = ws_emu(ws);
353	0	wa = VTAILQ_LAST(&we->head, ws_alloc_head);
354	0	CHECK_OBJ_ORNULL(wa, WS_ALLOC_MAGIC);
355	0	p = (wa == NULL ? ws->s : wa->ptr);
356	0	DSLb(DBG_WORKSPACE, "WS_Snapshot(%p) = %p", ws, p);
357	0	return ((uintptr_t)p);
358	0	}
359
360		unsigned
361	0	WS_ReserveAll(struct ws *ws)
362		{
363		struct ws_alloc *wa;
364		unsigned b;
365
366	0	wa = ws_emu_alloc(ws, 0);
367	0	AN(wa);
368
369	0	if (wa->ptr != NULL) {
370	0	AN(wa->len);
371	0	ws->f = wa->ptr;
372	0	ws->r = ws->f + wa->len;
373	0	} else {
374	0	ws->f = ws->r = ws->e;
375		}
376
377	0	b = pdiff(ws->f, ws->r);
378	0	DSLb(DBG_WORKSPACE, "WS_ReserveAll(%p) = %u", ws, b);
379	0	WS_Assert(ws);
380	0	return (b);
381		}
382
383		unsigned
384	0	WS_ReserveSize(struct ws *ws, unsigned bytes)
385		{
386		struct ws_emu *we;
387		struct ws_alloc *wa;
388
389	0	assert(bytes > 0);
390	0	wa = ws_emu_alloc(ws, bytes);
391	0	if (wa == NULL)
392	0	return (0);
393
394	0	AN(wa->ptr);
395	0	assert(wa->len == bytes);
396	0	ws->f = wa->ptr;
397	0	ws->r = ws->f + bytes;
398	0	we = ws_emu(ws);
399	0	DSLb(DBG_WORKSPACE, "WS_ReserveSize(%p, %u/%u) = %u",
400		ws, bytes, we->len - wa->off, bytes);
401	0	WS_Assert(ws);
402	0	return (bytes);
403	0	}
404
405		static void
406	0	ws_release(struct ws *ws, unsigned bytes)
407		{
408		struct ws_emu *we;
409		struct ws_alloc *wa;
410
411	0	WS_Assert(ws);
412	0	AN(ws->f);
413	0	AN(ws->r);
414	0	we = ws_emu(ws);
415	0	wa = VTAILQ_LAST(&we->head, ws_alloc_head);
416	0	AN(wa);
417	0	assert(bytes <= wa->len);
418	0	ws->f = ws->r = NULL;
419
420	0	if (bytes == 0) {
421	0	ws_alloc_free(we, &wa);
422	0	return;
423		}
424
425	0	AN(wa->ptr);
426		#ifdef ASAN_POISON_MEMORY_REGION
427		ASAN_POISON_MEMORY_REGION(wa->ptr + bytes, wa->len - bytes);
428		#endif
429	0	wa->len = bytes;
430	0	WS_Assert(ws);
431	0	}
432
433		void
434	0	WS_Release(struct ws *ws, unsigned bytes)
435		{
436
437	0	ws_release(ws, bytes);
438	0	DSLb(DBG_WORKSPACE, "WS_Release(%p, %u)", ws, bytes);
439	0	}
440
441		void
442	0	WS_ReleaseP(struct ws ws, const char ptr)
443		{
444		unsigned l;
445
446	0	WS_Assert(ws);
447	0	assert(ws->r != NULL);
448	0	assert(ptr >= ws->f);
449	0	assert(ptr <= ws->r);
450	0	l = pdiff(ws->f, ptr);
451	0	ws_release(ws, l);
452	0	DSLb(DBG_WORKSPACE, "WS_ReleaseP(%p, %p (%u))", ws, ptr, l);
453	0	}
454
455		void *
456	0	WS_AtOffset(const struct ws *ws, unsigned off, unsigned len)
457		{
458		struct ws_emu *we;
459		struct ws_alloc *wa;
460
461	0	WS_Assert(ws);
462	0	we = ws_emu(ws);
463
464	0	VTAILQ_FOREACH(wa, &we->head, list) {
465	0	if (wa->off == off) {
466	0	assert(wa->len >= len);
467	0	return (wa->ptr);
468		}
469	0	}
470
471	0	WRONG("invalid offset");
472	0	NEEDLESS(return (NULL));
473	0	}
474
475		unsigned
476	0	WS_ReservationOffset(const struct ws *ws)
477		{
478		struct ws_emu *we;
479		struct ws_alloc *wa;
480
481	0	WS_Assert(ws);
482	0	AN(ws->f);
483	0	AN(ws->r);
484	0	we = ws_emu(ws);
485	0	wa = VTAILQ_LAST(&we->head, ws_alloc_head);
486	0	AN(wa);
487	0	return (wa->off);
488		}
489
490		unsigned
491	0	WS_Dump(const struct ws ws, char where, size_t off, void buf, size_t len)
492		{
493		struct ws_emu *we;
494		struct ws_alloc *wa;
495		unsigned l;
496		char *b;
497
498	0	WS_Assert(ws);
499	0	AN(buf);