Page MenuHomeFreeBSD
Differential D28212

linux: implement PTRACE_GET_SYSCALL_INFO
ClosedPublic
Actions

Authored by trasz on Jan 17 2021, 6:17 PM.
Tags
None
Referenced Files
Unknown Object (File)
Mar 9 2025, 3:15 AM
Unknown Object (File)
Mar 5 2025, 3:10 PM
Unknown Object (File)
Mar 4 2025, 6:01 PM
Unknown Object (File)
Feb 27 2025, 8:28 PM
Unknown Object (File)
Feb 26 2025, 3:26 PM
Unknown Object (File)
Feb 25 2025, 6:42 PM
Unknown Object (File)
Feb 25 2025, 11:51 AM
Unknown Object (File)
Feb 23 2025, 9:37 PM
View All Files
Subscribers
emaste
imp
jrtc27

Details

Reviewers
jhb
Group Reviewers
Linux Emulation
Commits
rG8371bf67d632: linux: implement PTRACE_GET_SYSCALL_INFO
rGbdf0f24bb16d: linux: implement PTRACE_GET_SYSCALL_INFO
Summary

This is one of the pieces required to make modern (ie Focal)
strace(1) work.

Sponsored by: The FreeBSD Foundation

Diff Detail

Repository
rS FreeBSD src repository - subversion
Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 41478
Build 38367: arc lint + arc unit

Event Timeline

trasz created this revision.Jan 17 2021, 6:17 PM
Herald added subscribers: emaste, imp. · View Herald TranscriptJan 17 2021, 6:17 PM
trasz requested review of this revision.Jan 17 2021, 6:17 PM
Harbormaster completed remote builds in B36298: Diff 82430.Jan 17 2021, 6:17 PM
trasz added reviewers: Linux Emulation, jhb.Jan 17 2021, 6:18 PM
trasz updated this revision to Diff 82431.Jan 17 2021, 6:21 PM

Remove debugging printf.

Harbormaster completed remote builds in B36299: Diff 82431.Jan 17 2021, 6:21 PM
emaste added inline comments.Jan 17 2021, 6:41 PM
sys/amd64/linux/linux_ptrace.c
96–98

Are these MD?

trasz added inline comments.Jan 18 2021, 11:19 AM
sys/amd64/linux/linux_ptrace.c
96–98

I'm guessing they are not, but for now all of amd64 implementation of ptrace is in a MD-file. This will probably change once it gets ported to arm64.

jhb added inline comments.Jan 20 2021, 4:22 PM
sys/amd64/linux/linux_ptrace.c
571

This should never occur as FreeBSD doesn't use negative errno values. I think instead you should make the previous 'sr.sr_error > 0' into an else as the only conditions are 'sr.sr_error == 0' and 'sr.sr_error != 0'.

580

I would move the kern_ptrace of PT_REG down to here where you actually use it. Presumably, this block to set ip/sp would end up being MD, but the rest of this function is MI and should be shared across platforms.

sys/kern/sys_process.c
1015

This is a regression I believe as you would potentially leak earlier syscall arguments (albeit from the same thread). Certainly it is not part of this commit and would need to be its own commit, but I don't really think it's a good idea to change.

trasz added inline comments.Jan 20 2021, 7:39 PM
sys/amd64/linux/linux_ptrace.c
571

Thanks for clarifying this.

580

I agree about the block placement. I'd prefer not splitting this into MI/MD chunks just yet, there might be some unexplained differences in operation between versions - like with syscall numbers in Linux.

sys/kern/sys_process.c
1015

The reason for this chunk is that's what's expected by Linux strace(1).

What it does is, at initialization it tests whether ptrace works as expected; in this case it calls... I think close(2), or some other single-argument syscall, _with six arguments_, and then verifies whether it can fetch them using this API; otherwise it just bails out.

How much of a problem is this leak? Do we always clear the arguments on, say, execve(2)?

jhb added inline comments.Jan 21 2021, 6:36 PM
sys/kern/sys_process.c
1015

The reason for this chunk is that's what's expected by Linux strace(1).

What it does is, at initialization it tests whether ptrace works as expected; in this case it calls... I think close(2), or some other single-argument syscall, _with six arguments_, and then verifies whether it can fetch them using this API; otherwise it just bails out.

How much of a problem is this leak? Do we always clear the arguments on, say, execve(2)?

That's horrible. What horrible code. I don't want to break perfectly good FreeBSD code to cater to such nonsense. You can either add a private PT_GET_SC_ARGS_RAW for Linux to use that does this, or handle this directly in the Linux code by reading from td_sa without using kern_ptrace().

jrtc27 added a subscriber: jrtc27.Jan 22 2021, 6:21 PM
jrtc27 added inline comments.
sys/kern/sys_process.c
1015

Depends what architecture you're on (i.e. whether some syscall arguments go on the stack). If everything is passed in registers we just copy the whole trapframe's worth, so you'd "just" be leaking arguments that happened to be in the later argument registers, not things from way earlier that the tracee no longer even necessarily has (well, except for syscall(2) itself, that ends up copying one fewer argument, so if that was the last syscall then you'll leak the previous syscall's last register).

imp mentioned this in D28612: git-arc: Use a separate message file.Feb 12 2021, 5:30 PM
trasz mentioned this in D30457: linuxulator: Some ptrace fixes...Jun 9 2021, 12:41 PM
trasz updated this revision to Diff 91817.Jul 5 2021, 5:51 PM

Fix problems reported by jhb@, also style(9).

Harbormaster completed remote builds in B40319: Diff 91817.Jul 5 2021, 5:51 PM
trasz added a comment.Aug 17 2021, 8:56 AM

Ping?

jhb added inline comments.Aug 17 2021, 4:01 PM
sys/kern/sys_process.c
492

I think this should not be enabled for ptrace() for native binaries, only an internal operation for Linux ABI to use. That means though that sys_ptrace() has to explicitly fail this request here with EINVAL. freebsd32_ptrace() also needs updating to fail this request.

sys/sys/ptrace.h
89

Perhaps #ifdef _KERNEL around this?

trasz updated this revision to Diff 94848.Sep 7 2021, 4:51 PM

More fixes.

Harbormaster completed remote builds in B41422: Diff 94848.Sep 7 2021, 4:51 PM
trasz updated this revision to Diff 94849.Sep 7 2021, 5:27 PM
trasz marked 2 inline comments as done.

Handle freebsd32.

Harbormaster completed remote builds in B41423: Diff 94849.Sep 7 2021, 5:27 PM
jhb accepted this revision.Sep 8 2021, 6:21 PM
This revision is now accepted and ready to land.Sep 8 2021, 6:21 PM
trasz added a comment.Sep 12 2021, 8:40 PM

There's still one problem: the #ifdef _KERNEL breaks world build (lib/libsysdecode/tables.h:406:13: error: use of undeclared identifier 'PT_GET_SC_ARGS_ALL'). Is there already some #define to allow libsysdecode to use kernel includes, or is there a different way?

jrtc27 added a comment.Sep 12 2021, 8:45 PM
In D28212#720209, @trasz wrote:

There's still one problem: the #ifdef _KERNEL breaks world build (lib/libsysdecode/tables.h:406:13: error: use of undeclared identifier 'PT_GET_SC_ARGS_ALL'). Is there already some #define to allow libsysdecode to use kernel includes, or is there a different way?

You can edit lib/libsysdecode/mktables to exclude it; the optional fourth argument to gen_table is a regex passed to egrep -v.

trasz updated this revision to Diff 95039.Sep 13 2021, 1:30 PM

Fix buildworld.

This revision now requires review to proceed.Sep 13 2021, 1:30 PM
Harbormaster completed remote builds in B41478: Diff 95039.Sep 13 2021, 1:30 PM
This revision was not accepted when it landed; it landed in state Needs Review.Sep 14 2021, 8:42 PM
Closed by commit rGbdf0f24bb16d: linux: implement PTRACE_GET_SYSCALL_INFO (authored by trasz). · Explain Why
This revision was automatically updated to reflect the committed changes.
trasz added a commit: rGbdf0f24bb16d: linux: implement PTRACE_GET_SYSCALL_INFO.
trasz added a commit: rG8371bf67d632: linux: implement PTRACE_GET_SYSCALL_INFO.Feb 21 2022, 1:49 PM

Revision Contents
Changeset List

PathSize
lib/
libsysdecode/
2 lines
sys/
amd64/
linux/
98 lines
compat/
freebsd32/
3 lines
kern/
17 lines
sys/
4 lines

Diff 95039

View Options

lib/libsysdecode/mktables

Context not available.
#include <sys/kernel.h> #include <sys/kernel.h>
#include <sys/blist.h> #include <sys/blist.h>
#include <sys/malloc.h> #include <sys/malloc.h>
#include <sys/sbuf.h>
#include <sys/proc.h> #include <sys/proc.h>
#include <sys/mutex.h> #include <sys/mutex.h>
alcUnsubmitted
Not Done
Inline Actions

This should be <sys/sbuf.h>

alc: This should be <sys/sbuf.h>
Context not available.
#include <sys/types.h> #include <sys/types.h>
#include <sys/malloc.h> #include <sys/malloc.h>
#include <sys/sbuf.h>
#include <stdio.h> #include <stdio.h>
#include <string.h> #include <string.h>
#include <stdlib.h> #include <stdlib.h>
Context not available.
#endif #endif
CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0); CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0);
#define BLIST_META_MASK (BLIST_META_RADIX - 1)
/* /*
* For a subtree that can represent the state of up to 'radix' blocks, the * For a subtree that can represent the state of up to 'radix' blocks, the
Context not available.
{ {
return (radix / return (radix /
((BLIST_BMAP_RADIX / BLIST_META_RADIX) * (BLIST_META_RADIX - 1))); ((BLIST_BMAP_RADIX / BLIST_META_RADIX) * BLIST_META_MASK));
}
/*
* Use binary search to find the 1 bit in a u_daddr_t.
* Assumes that the argument has only one bit set. ffs(x)
* could be implemented as return (x==0? 0: 1+bitpos(x&-x)).
*/
static inline int
bitpos(u_daddr_t mask)
{
int hi, lo, mid;
switch (sizeof(u_daddr_t)) {
#ifdef HAVE_INLINE_FFSLL
case sizeof(long long):
return (ffsll(mask) - 1);
#endif
default:
lo = 0;
hi = BLIST_BMAP_RADIX;
while (lo + 1 < hi) {
mid = (lo + hi) >> 1;
if ((mask >> mid) != 0)
lo = mid;
else
hi = mid;
}
return (lo);
}
} }
/* /*
Context not available.
#endif #endif
struct gap_stats {
int num; /* number of gaps observed */
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
alcUnsubmitted
Not Done
Inline Actions

If every other block is allocated, this field can overflow.

alc: If every other block is allocated, this field can overflow.
daddr_t max; /* largest gap size */
daddr_t avg; /* average gap size */
daddr_t err; /* sum - num * avg */
int histo[127]; /* counts for gaps of various sizes */
int max_bucket;
u_daddr_t start;
};
alcUnsubmitted
Not Done
Inline Actions

Incorrect indentation.

alc: Incorrect indentation.
/*
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
* gap_stats_counting() - is the state 'counting 1 bits'?
* or 'skipping 0 bits'?
*/
static inline int
gap_stats_counting(struct gap_stats *stats)
{
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
return (stats->start != -1);
alcUnsubmitted
Not Done
Inline Actions

Insert a blank line before the bzero().

alc: Insert a blank line before the bzero().
}
/*
* init_gap_stats() - initialize stats on gap sizes
*/
alcUnsubmitted
Done
Inline Actions

It is probably better to bzero() the entire structure and then initialize "start".

alc: It is probably better to bzero() the entire structure and then initialize "start".
static inline void
init_gap_stats(struct gap_stats *stats)
alcUnsubmitted
Done
Inline Actions

Insert blank line.

alc: Insert blank line.
{
bzero(stats, sizeof(*stats));
stats->start = -1;
}
/*
* update_gap_stats() - update stats on gap sizes
alcUnsubmitted
Done
Inline Actions

The u_daddr_t definition should come first because it is a larger data type.

alc: The u_daddr_t definition should come first because it is a larger data type.
*/
static void
update_gap_stats(struct gap_stats *stats, u_daddr_t posn)
{
u_daddr_t size;
int id, logsize;
if (!gap_stats_counting(stats)) {
stats->start = posn;
return;
}
size = posn - stats->start;
stats->start = -1;
if (size > stats->max)
alcUnsubmitted
Not Done
Inline Actions

This will probably need to change, but it can wait for a future revision.

alc: This will probably need to change, but it can wait for a future revision.
stats->max = size;
if (size == 1) {
id = 0;
alcUnsubmitted
Done
Inline Actions

Use postfix instead.

alc: Use postfix instead.
} else {
logsize = 1;
while ((size >> logsize) > 1)
logsize++;
id = 2 * logsize - 1;
if (size >> (logsize - 1) >= 3)
alcUnsubmitted
Done
Inline Actions

Use postfix.

alc: Use postfix.
id++;
}
stats->histo[id]++;
if (id > stats->max_bucket)
stats->max_bucket = id;
stats->err += (daddr_t)size - stats->avg;
stats->num++;
stats->avg += stats->err / stats->num;
stats->err %= stats->num;
}
alcUnsubmitted
Done
Inline Actions

Insert blank line.

alc: Insert blank line.
alcUnsubmitted
Not Done
Inline Actions

You need to use "%ju" and uintmax_t.

alc: You need to use "%ju" and uintmax_t.
/*
* dump_stats() - print stats on gap sizes
*/
static inline void
dump_gap_stats(struct sbuf *s, struct gap_stats *stats)
{
int i, val;
sbuf_printf(s, "number of gaps: %d\n", stats->num);
alcUnsubmitted
Done
Inline Actions

The outermost parens around the expression are not needed. Spaces are required around binary operators.

alc: The outermost parens around the expression are not needed. Spaces are required around binary…
sbuf_printf(s, "largest gap: %jd\n", (intmax_t)stats->max);
sbuf_printf(s, "average gap size: %jd\n", (intmax_t)stats->avg);
sbuf_printf(s, "histogram:\n");
for (i = 0; i <= stats->max_bucket; i++) {
val = (i == 0) ? 1 : ((3 - i % 2) << ((i - 1) / 2));
sbuf_printf(s, "%d\t%d\n", val, stats->histo[i]);
}
}
/*
* blist_stats() - dump radix tree stats
alcUnsubmitted
Not Done
Inline Actions

This needs to be declared in blist.h.

alc: This needs to be declared in blist.h.
*/
void
blist_stats(struct sbuf *s, blist_t bl)
{
alcUnsubmitted
Done
Inline Actions

The struct should come first.

alc: The struct should come first.
daddr_t bit, diff, i, nodes, radix;
u_daddr_t mask;
struct gap_stats stats;
init_gap_stats(&stats);
nodes = 0;
i = bl->bl_radix;
while (i < bl->bl_radix + bl->bl_blocks) {
radix = BLIST_BMAP_RADIX;
while (((i / radix) & BLIST_META_MASK) == 0) {
/*
* Skip meta node.
*/
radix *= BLIST_META_RADIX;
}
while (radix > BLIST_BMAP_RADIX) {
if (bl->bl_root[nodes].u.bmu_avail == 0) {
if (gap_stats_counting(&stats))
update_gap_stats(&stats, i);
break;
}
if (bl->bl_root[nodes].u.bmu_avail == radix) {
if (!gap_stats_counting(&stats))
update_gap_stats(&stats, i);
break;
}
nodes++;
radix /= BLIST_META_RADIX;
}
if (radix == BLIST_BMAP_RADIX) {
/*
* Scan leaf.
*/
mask = bl->bl_root[nodes].u.bmu_bitmap;
diff = mask ^ (mask << 1);
diff ^= gap_stats_counting(&stats);
while (diff) {
bit = diff & -diff;
update_gap_stats(&stats, i + bitpos(bit));
diff ^= bit;
}
}
nodes += radix_to_skip(radix);
i += radix;
}
update_gap_stats(&stats, i);
dump_gap_stats(s, &stats);
}
/************************************************************************ /************************************************************************
* ALLOCATION SUPPORT FUNCTIONS * * ALLOCATION SUPPORT FUNCTIONS *
************************************************************************ ************************************************************************
alcUnsubmitted
Not Done
Inline Actions

This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy(), or swp_pager_freeswapspace().

alc: This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy…
Context not available.
* *
* This is the core of the allocator and is optimized for the * This is the core of the allocator and is optimized for the
* BLIST_BMAP_RADIX block allocation case. Otherwise, execution * BLIST_BMAP_RADIX block allocation case. Otherwise, execution
* time is proportional to log2(count) + log2(BLIST_BMAP_RADIX). * time is proportional to log2(count) + bitpos time.
*/ */
static daddr_t static daddr_t
blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor) blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor)
{ {
u_daddr_t mask; u_daddr_t mask;
int count1, hi, lo, mid, num_shifts, range1, range_ext; int count1, lo, num_shifts, range1, range_ext;
if (count == BLIST_BMAP_RADIX) { if (count == BLIST_BMAP_RADIX) {
/* /*
Context not available.
/* /*
* The least significant set bit in mask marks the start of the first * The least significant set bit in mask marks the start of the first
* available range of sufficient size. Clear all the bits but that one, * available range of sufficient size. Clear all the bits but that one,
* and then perform a binary search to find its position. * and then find its position.
*/ */
mask &= -mask; mask &= -mask;
hi = BLIST_BMAP_RADIX - count1; lo = bitpos(mask);
while (lo + 1 < hi) {
mid = (lo + hi) >> 1;
if ((mask >> mid) != 0)
lo = mid;
else
hi = mid;
}
/* /*
* Set in mask exactly the bits being allocated, and clear them from * Set in mask exactly the bits being allocated, and clear them from
Context not available.
int size = 1024; int size = 1024;
int i; int i;
blist_t bl; blist_t bl;
struct sbuf *s;
for (i = 1; i < ac; ++i) { for (i = 1; i < ac; ++i) {
const char *ptr = av[i]; const char *ptr = av[i];
Context not available.
case 'p': case 'p':
blist_print(bl); blist_print(bl);
break; break;
case 's':
s = sbuf_new_auto();
blist_stats(s, bl);
sbuf_finish(s);
printf("%s", sbuf_data(s));
sbuf_delete(s);
break;
case 'a': case 'a':
if (sscanf(buf + 1, "%lld", &count) == 1) { if (sscanf(buf + 1, "%lld", &count) == 1) {
daddr_t blk = blist_alloc(bl, count); daddr_t blk = blist_alloc(bl, count);
Context not available.
case 'h': case 'h':
puts( puts(
"p -print\n" "p -print\n"
"s -stats\n"
"a %d -allocate\n" "a %d -allocate\n"
"f %x %d -free\n" "f %x %d -free\n"
"l %x %d -fill\n" "l %x %d -fill\n"
Context not available.
View Options

sys/amd64/linux/linux_ptrace.c

Context not available.
#include <sys/kernel.h> #include <sys/kernel.h>
#include <sys/blist.h> #include <sys/blist.h>
#include <sys/malloc.h> #include <sys/malloc.h>
#include <sys/sbuf.h>
#include <sys/proc.h> #include <sys/proc.h>
#include <sys/mutex.h> #include <sys/mutex.h>
alcUnsubmitted
Not Done
Inline Actions

This should be <sys/sbuf.h>

alc: This should be <sys/sbuf.h>
Context not available.
#include <sys/types.h> #include <sys/types.h>
#include <sys/malloc.h> #include <sys/malloc.h>
#include <sys/sbuf.h>
#include <stdio.h> #include <stdio.h>
#include <string.h> #include <string.h>
#include <stdlib.h> #include <stdlib.h>
Context not available.
#endif #endif
CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0); CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0);
#define BLIST_META_MASK (BLIST_META_RADIX - 1)
/* /*
* For a subtree that can represent the state of up to 'radix' blocks, the * For a subtree that can represent the state of up to 'radix' blocks, the
Context not available.
{ {
return (radix / return (radix /
((BLIST_BMAP_RADIX / BLIST_META_RADIX) * (BLIST_META_RADIX - 1))); ((BLIST_BMAP_RADIX / BLIST_META_RADIX) * BLIST_META_MASK));
}
/*
* Use binary search to find the 1 bit in a u_daddr_t.
* Assumes that the argument has only one bit set. ffs(x)
* could be implemented as return (x==0? 0: 1+bitpos(x&-x)).
*/
static inline int
bitpos(u_daddr_t mask)
{
int hi, lo, mid;
switch (sizeof(u_daddr_t)) {
#ifdef HAVE_INLINE_FFSLL
case sizeof(long long):
return (ffsll(mask) - 1);
#endif
default:
lo = 0;
hi = BLIST_BMAP_RADIX;
while (lo + 1 < hi) {
mid = (lo + hi) >> 1;
if ((mask >> mid) != 0)
lo = mid;
else
hi = mid;
}
return (lo);
}
} }
/* /*
Context not available.
#endif #endif
struct gap_stats {
int num; /* number of gaps observed */
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
alcUnsubmitted
Not Done
Inline Actions

If every other block is allocated, this field can overflow.

alc: If every other block is allocated, this field can overflow.
daddr_t max; /* largest gap size */
daddr_t avg; /* average gap size */
daddr_t err; /* sum - num * avg */
int histo[127]; /* counts for gaps of various sizes */
int max_bucket;
u_daddr_t start;
};
alcUnsubmitted
Not Done
Inline Actions

Incorrect indentation.

alc: Incorrect indentation.
/*
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
* gap_stats_counting() - is the state 'counting 1 bits'?
* or 'skipping 0 bits'?
*/
static inline int
gap_stats_counting(struct gap_stats *stats)
{
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
return (stats->start != -1);
alcUnsubmitted
Not Done
Inline Actions

Insert a blank line before the bzero().

alc: Insert a blank line before the bzero().
}
/*
* init_gap_stats() - initialize stats on gap sizes
*/
alcUnsubmitted
Done
Inline Actions

It is probably better to bzero() the entire structure and then initialize "start".

alc: It is probably better to bzero() the entire structure and then initialize "start".
static inline void
init_gap_stats(struct gap_stats *stats)
alcUnsubmitted
Done
Inline Actions

Insert blank line.

alc: Insert blank line.
{
bzero(stats, sizeof(*stats));
stats->start = -1;
}
/*
* update_gap_stats() - update stats on gap sizes
alcUnsubmitted
Done
Inline Actions

The u_daddr_t definition should come first because it is a larger data type.

alc: The u_daddr_t definition should come first because it is a larger data type.
*/
static void
update_gap_stats(struct gap_stats *stats, u_daddr_t posn)
{
u_daddr_t size;
int id, logsize;
if (!gap_stats_counting(stats)) {
stats->start = posn;
return;
}
size = posn - stats->start;
stats->start = -1;
if (size > stats->max)
alcUnsubmitted
Not Done
Inline Actions

This will probably need to change, but it can wait for a future revision.

alc: This will probably need to change, but it can wait for a future revision.
stats->max = size;
if (size == 1) {
id = 0;
alcUnsubmitted
Done
Inline Actions

Use postfix instead.

alc: Use postfix instead.
} else {
logsize = 1;
while ((size >> logsize) > 1)
logsize++;
id = 2 * logsize - 1;
if (size >> (logsize - 1) >= 3)
alcUnsubmitted
Done
Inline Actions

Use postfix.

alc: Use postfix.
id++;
}
stats->histo[id]++;
if (id > stats->max_bucket)
stats->max_bucket = id;
stats->err += (daddr_t)size - stats->avg;
stats->num++;
stats->avg += stats->err / stats->num;
stats->err %= stats->num;
}
alcUnsubmitted
Done
Inline Actions

Insert blank line.

alc: Insert blank line.
alcUnsubmitted
Not Done
Inline Actions

You need to use "%ju" and uintmax_t.

alc: You need to use "%ju" and uintmax_t.
/*
* dump_stats() - print stats on gap sizes
*/
static inline void
dump_gap_stats(struct sbuf *s, struct gap_stats *stats)
{
int i, val;
sbuf_printf(s, "number of gaps: %d\n", stats->num);
alcUnsubmitted
Done
Inline Actions

The outermost parens around the expression are not needed. Spaces are required around binary operators.

alc: The outermost parens around the expression are not needed. Spaces are required around binary…
sbuf_printf(s, "largest gap: %jd\n", (intmax_t)stats->max);
sbuf_printf(s, "average gap size: %jd\n", (intmax_t)stats->avg);
sbuf_printf(s, "histogram:\n");
for (i = 0; i <= stats->max_bucket; i++) {
val = (i == 0) ? 1 : ((3 - i % 2) << ((i - 1) / 2));
sbuf_printf(s, "%d\t%d\n", val, stats->histo[i]);
}
}
/*
* blist_stats() - dump radix tree stats
alcUnsubmitted
Not Done
Inline Actions

This needs to be declared in blist.h.

alc: This needs to be declared in blist.h.
*/
void
blist_stats(struct sbuf *s, blist_t bl)
{
alcUnsubmitted
Done
Inline Actions

The struct should come first.

alc: The struct should come first.
daddr_t bit, diff, i, nodes, radix;
u_daddr_t mask;
struct gap_stats stats;
init_gap_stats(&stats);
nodes = 0;
i = bl->bl_radix;
while (i < bl->bl_radix + bl->bl_blocks) {
radix = BLIST_BMAP_RADIX;
while (((i / radix) & BLIST_META_MASK) == 0) {
/*
* Skip meta node.
*/
radix *= BLIST_META_RADIX;
}
while (radix > BLIST_BMAP_RADIX) {
if (bl->bl_root[nodes].u.bmu_avail == 0) {
if (gap_stats_counting(&stats))
update_gap_stats(&stats, i);
break;
}
if (bl->bl_root[nodes].u.bmu_avail == radix) {
if (!gap_stats_counting(&stats))
update_gap_stats(&stats, i);
break;
}
nodes++;
radix /= BLIST_META_RADIX;
}
if (radix == BLIST_BMAP_RADIX) {
/*
* Scan leaf.
*/
mask = bl->bl_root[nodes].u.bmu_bitmap;
diff = mask ^ (mask << 1);
diff ^= gap_stats_counting(&stats);
while (diff) {
bit = diff & -diff;
update_gap_stats(&stats, i + bitpos(bit));
diff ^= bit;
}
}
nodes += radix_to_skip(radix);
i += radix;
}
update_gap_stats(&stats, i);
dump_gap_stats(s, &stats);
}
/************************************************************************ /************************************************************************
* ALLOCATION SUPPORT FUNCTIONS * * ALLOCATION SUPPORT FUNCTIONS *
************************************************************************ ************************************************************************
alcUnsubmitted
Not Done
Inline Actions

This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy(), or swp_pager_freeswapspace().

alc: This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy…
Context not available.
* *
* This is the core of the allocator and is optimized for the * This is the core of the allocator and is optimized for the
* BLIST_BMAP_RADIX block allocation case. Otherwise, execution * BLIST_BMAP_RADIX block allocation case. Otherwise, execution
* time is proportional to log2(count) + log2(BLIST_BMAP_RADIX). * time is proportional to log2(count) + bitpos time.
*/ */
static daddr_t static daddr_t
blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor) blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor)
{ {
u_daddr_t mask; u_daddr_t mask;
int count1, hi, lo, mid, num_shifts, range1, range_ext; int count1, lo, num_shifts, range1, range_ext;
if (count == BLIST_BMAP_RADIX) { if (count == BLIST_BMAP_RADIX) {
/* /*
Context not available.
/* /*
* The least significant set bit in mask marks the start of the first * The least significant set bit in mask marks the start of the first
* available range of sufficient size. Clear all the bits but that one, * available range of sufficient size. Clear all the bits but that one,
* and then perform a binary search to find its position. * and then find its position.
*/ */
mask &= -mask; mask &= -mask;
hi = BLIST_BMAP_RADIX - count1; lo = bitpos(mask);
while (lo + 1 < hi) {
mid = (lo + hi) >> 1;
if ((mask >> mid) != 0)
lo = mid;
else
hi = mid;
}
/* /*
* Set in mask exactly the bits being allocated, and clear them from * Set in mask exactly the bits being allocated, and clear them from
Context not available.
int size = 1024; int size = 1024;
int i; int i;
blist_t bl; blist_t bl;
struct sbuf *s;
for (i = 1; i < ac; ++i) { for (i = 1; i < ac; ++i) {
const char *ptr = av[i]; const char *ptr = av[i];
Context not available.
case 'p': case 'p':
blist_print(bl); blist_print(bl);
break; break;
case 's':
s = sbuf_new_auto();
blist_stats(s, bl);
sbuf_finish(s);
printf("%s", sbuf_data(s));
sbuf_delete(s);
break;
case 'a': case 'a':
if (sscanf(buf + 1, "%lld", &count) == 1) { if (sscanf(buf + 1, "%lld", &count) == 1) {
daddr_t blk = blist_alloc(bl, count); daddr_t blk = blist_alloc(bl, count);
Context not available.
case 'h': case 'h':
puts( puts(
"p -print\n" "p -print\n"
"s -stats\n"
"a %d -allocate\n" "a %d -allocate\n"
"f %x %d -free\n" "f %x %d -free\n"
"l %x %d -fill\n" "l %x %d -fill\n"
Context not available.
View Options

sys/compat/freebsd32/freebsd32_misc.c

Context not available.
#include <sys/kernel.h> #include <sys/kernel.h>
#include <sys/blist.h> #include <sys/blist.h>
#include <sys/malloc.h> #include <sys/malloc.h>
#include <sys/sbuf.h>
#include <sys/proc.h> #include <sys/proc.h>
#include <sys/mutex.h> #include <sys/mutex.h>
alcUnsubmitted
Not Done
Inline Actions

This should be <sys/sbuf.h>

alc: This should be <sys/sbuf.h>
Context not available.
#include <sys/types.h> #include <sys/types.h>
#include <sys/malloc.h> #include <sys/malloc.h>
#include <sys/sbuf.h>
#include <stdio.h> #include <stdio.h>
#include <string.h> #include <string.h>
#include <stdlib.h> #include <stdlib.h>
Context not available.
#endif #endif
CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0); CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0);
#define BLIST_META_MASK (BLIST_META_RADIX - 1)
/* /*
* For a subtree that can represent the state of up to 'radix' blocks, the * For a subtree that can represent the state of up to 'radix' blocks, the
Context not available.
{ {
return (radix / return (radix /
((BLIST_BMAP_RADIX / BLIST_META_RADIX) * (BLIST_META_RADIX - 1))); ((BLIST_BMAP_RADIX / BLIST_META_RADIX) * BLIST_META_MASK));
}
/*
* Use binary search to find the 1 bit in a u_daddr_t.
* Assumes that the argument has only one bit set. ffs(x)
* could be implemented as return (x==0? 0: 1+bitpos(x&-x)).
*/
static inline int
bitpos(u_daddr_t mask)
{
int hi, lo, mid;
switch (sizeof(u_daddr_t)) {
#ifdef HAVE_INLINE_FFSLL
case sizeof(long long):
return (ffsll(mask) - 1);
#endif
default:
lo = 0;
hi = BLIST_BMAP_RADIX;
while (lo + 1 < hi) {
mid = (lo + hi) >> 1;
if ((mask >> mid) != 0)
lo = mid;
else
hi = mid;
}
return (lo);
}
} }
/* /*
Context not available.
#endif #endif
struct gap_stats {
int num; /* number of gaps observed */
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
alcUnsubmitted
Not Done
Inline Actions

If every other block is allocated, this field can overflow.

alc: If every other block is allocated, this field can overflow.
daddr_t max; /* largest gap size */
daddr_t avg; /* average gap size */
daddr_t err; /* sum - num * avg */
int histo[127]; /* counts for gaps of various sizes */
int max_bucket;
u_daddr_t start;
};
alcUnsubmitted
Not Done
Inline Actions

Incorrect indentation.

alc: Incorrect indentation.
/*
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
* gap_stats_counting() - is the state 'counting 1 bits'?
* or 'skipping 0 bits'?
*/
static inline int
gap_stats_counting(struct gap_stats *stats)
{
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
return (stats->start != -1);
alcUnsubmitted
Not Done
Inline Actions

Insert a blank line before the bzero().

alc: Insert a blank line before the bzero().
}
/*
* init_gap_stats() - initialize stats on gap sizes
*/
alcUnsubmitted
Done
Inline Actions

It is probably better to bzero() the entire structure and then initialize "start".

alc: It is probably better to bzero() the entire structure and then initialize "start".
static inline void
init_gap_stats(struct gap_stats *stats)
alcUnsubmitted
Done
Inline Actions

Insert blank line.

alc: Insert blank line.
{
bzero(stats, sizeof(*stats));
stats->start = -1;
}
/*
* update_gap_stats() - update stats on gap sizes
alcUnsubmitted
Done
Inline Actions

The u_daddr_t definition should come first because it is a larger data type.

alc: The u_daddr_t definition should come first because it is a larger data type.
*/
static void
update_gap_stats(struct gap_stats *stats, u_daddr_t posn)
{
u_daddr_t size;
int id, logsize;
if (!gap_stats_counting(stats)) {
stats->start = posn;
return;
}
size = posn - stats->start;
stats->start = -1;
if (size > stats->max)
alcUnsubmitted
Not Done
Inline Actions

This will probably need to change, but it can wait for a future revision.

alc: This will probably need to change, but it can wait for a future revision.
stats->max = size;
if (size == 1) {
id = 0;
alcUnsubmitted
Done
Inline Actions

Use postfix instead.

alc: Use postfix instead.
} else {
logsize = 1;
while ((size >> logsize) > 1)
logsize++;
id = 2 * logsize - 1;
if (size >> (logsize - 1) >= 3)
alcUnsubmitted
Done
Inline Actions

Use postfix.

alc: Use postfix.
id++;
}
stats->histo[id]++;
if (id > stats->max_bucket)
stats->max_bucket = id;
stats->err += (daddr_t)size - stats->avg;
stats->num++;
stats->avg += stats->err / stats->num;
stats->err %= stats->num;
}
alcUnsubmitted
Done
Inline Actions

Insert blank line.

alc: Insert blank line.
alcUnsubmitted
Not Done
Inline Actions

You need to use "%ju" and uintmax_t.

alc: You need to use "%ju" and uintmax_t.
/*
* dump_stats() - print stats on gap sizes
*/
static inline void
dump_gap_stats(struct sbuf *s, struct gap_stats *stats)
{
int i, val;
sbuf_printf(s, "number of gaps: %d\n", stats->num);
alcUnsubmitted
Done
Inline Actions

The outermost parens around the expression are not needed. Spaces are required around binary operators.

alc: The outermost parens around the expression are not needed. Spaces are required around binary…
sbuf_printf(s, "largest gap: %jd\n", (intmax_t)stats->max);
sbuf_printf(s, "average gap size: %jd\n", (intmax_t)stats->avg);
sbuf_printf(s, "histogram:\n");
for (i = 0; i <= stats->max_bucket; i++) {
val = (i == 0) ? 1 : ((3 - i % 2) << ((i - 1) / 2));
sbuf_printf(s, "%d\t%d\n", val, stats->histo[i]);
}
}
/*
* blist_stats() - dump radix tree stats
alcUnsubmitted
Not Done
Inline Actions

This needs to be declared in blist.h.

alc: This needs to be declared in blist.h.
*/
void
blist_stats(struct sbuf *s, blist_t bl)
{
alcUnsubmitted
Done
Inline Actions

The struct should come first.

alc: The struct should come first.
daddr_t bit, diff, i, nodes, radix;
u_daddr_t mask;
struct gap_stats stats;
init_gap_stats(&stats);
nodes = 0;
i = bl->bl_radix;
while (i < bl->bl_radix + bl->bl_blocks) {
radix = BLIST_BMAP_RADIX;
while (((i / radix) & BLIST_META_MASK) == 0) {
/*
* Skip meta node.
*/
radix *= BLIST_META_RADIX;
}
while (radix > BLIST_BMAP_RADIX) {
if (bl->bl_root[nodes].u.bmu_avail == 0) {
if (gap_stats_counting(&stats))
update_gap_stats(&stats, i);
break;
}
if (bl->bl_root[nodes].u.bmu_avail == radix) {
if (!gap_stats_counting(&stats))
update_gap_stats(&stats, i);
break;
}
nodes++;
radix /= BLIST_META_RADIX;
}
if (radix == BLIST_BMAP_RADIX) {
/*
* Scan leaf.
*/
mask = bl->bl_root[nodes].u.bmu_bitmap;
diff = mask ^ (mask << 1);
diff ^= gap_stats_counting(&stats);
while (diff) {
bit = diff & -diff;
update_gap_stats(&stats, i + bitpos(bit));
diff ^= bit;
}
}
nodes += radix_to_skip(radix);
i += radix;
}
update_gap_stats(&stats, i);
dump_gap_stats(s, &stats);
}
/************************************************************************ /************************************************************************
* ALLOCATION SUPPORT FUNCTIONS * * ALLOCATION SUPPORT FUNCTIONS *
************************************************************************ ************************************************************************
alcUnsubmitted
Not Done
Inline Actions

This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy(), or swp_pager_freeswapspace().

alc: This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy…
Context not available.
* *
* This is the core of the allocator and is optimized for the * This is the core of the allocator and is optimized for the
* BLIST_BMAP_RADIX block allocation case. Otherwise, execution * BLIST_BMAP_RADIX block allocation case. Otherwise, execution
* time is proportional to log2(count) + log2(BLIST_BMAP_RADIX). * time is proportional to log2(count) + bitpos time.
*/ */
static daddr_t static daddr_t
blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor) blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor)
{ {
u_daddr_t mask; u_daddr_t mask;
int count1, hi, lo, mid, num_shifts, range1, range_ext; int count1, lo, num_shifts, range1, range_ext;
if (count == BLIST_BMAP_RADIX) { if (count == BLIST_BMAP_RADIX) {
/* /*
Context not available.
/* /*
* The least significant set bit in mask marks the start of the first * The least significant set bit in mask marks the start of the first
* available range of sufficient size. Clear all the bits but that one, * available range of sufficient size. Clear all the bits but that one,
* and then perform a binary search to find its position. * and then find its position.
*/ */
mask &= -mask; mask &= -mask;
hi = BLIST_BMAP_RADIX - count1; lo = bitpos(mask);
while (lo + 1 < hi) {
mid = (lo + hi) >> 1;
if ((mask >> mid) != 0)
lo = mid;
else
hi = mid;
}
/* /*
* Set in mask exactly the bits being allocated, and clear them from * Set in mask exactly the bits being allocated, and clear them from
Context not available.
int size = 1024; int size = 1024;
int i; int i;
blist_t bl; blist_t bl;
struct sbuf *s;
for (i = 1; i < ac; ++i) { for (i = 1; i < ac; ++i) {
const char *ptr = av[i]; const char *ptr = av[i];
Context not available.
case 'p': case 'p':
blist_print(bl); blist_print(bl);
break; break;
case 's':
s = sbuf_new_auto();
blist_stats(s, bl);
sbuf_finish(s);
printf("%s", sbuf_data(s));
sbuf_delete(s);
break;
case 'a': case 'a':
if (sscanf(buf + 1, "%lld", &count) == 1) { if (sscanf(buf + 1, "%lld", &count) == 1) {
daddr_t blk = blist_alloc(bl, count); daddr_t blk = blist_alloc(bl, count);
Context not available.
case 'h': case 'h':
puts( puts(
"p -print\n" "p -print\n"
"s -stats\n"
"a %d -allocate\n" "a %d -allocate\n"
"f %x %d -free\n" "f %x %d -free\n"
"l %x %d -fill\n" "l %x %d -fill\n"
Context not available.
View Options

sys/kern/sys_process.c

Context not available.
#include <sys/kernel.h> #include <sys/kernel.h>
#include <sys/blist.h> #include <sys/blist.h>
#include <sys/malloc.h> #include <sys/malloc.h>
#include <sys/sbuf.h>
#include <sys/proc.h> #include <sys/proc.h>
#include <sys/mutex.h> #include <sys/mutex.h>
alcUnsubmitted
Not Done
Inline Actions

This should be <sys/sbuf.h>

alc: This should be <sys/sbuf.h>
Context not available.
#include <sys/types.h> #include <sys/types.h>
#include <sys/malloc.h> #include <sys/malloc.h>
#include <sys/sbuf.h>
#include <stdio.h> #include <stdio.h>
#include <string.h> #include <string.h>
#include <stdlib.h> #include <stdlib.h>
Context not available.
#endif #endif
CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0); CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0);
#define BLIST_META_MASK (BLIST_META_RADIX - 1)
/* /*
* For a subtree that can represent the state of up to 'radix' blocks, the * For a subtree that can represent the state of up to 'radix' blocks, the
Context not available.
{ {
return (radix / return (radix /
((BLIST_BMAP_RADIX / BLIST_META_RADIX) * (BLIST_META_RADIX - 1))); ((BLIST_BMAP_RADIX / BLIST_META_RADIX) * BLIST_META_MASK));
}
/*
* Use binary search to find the 1 bit in a u_daddr_t.
* Assumes that the argument has only one bit set. ffs(x)
* could be implemented as return (x==0? 0: 1+bitpos(x&-x)).
*/
static inline int
bitpos(u_daddr_t mask)
{
int hi, lo, mid;
switch (sizeof(u_daddr_t)) {
#ifdef HAVE_INLINE_FFSLL
case sizeof(long long):
return (ffsll(mask) - 1);
#endif
default:
lo = 0;
hi = BLIST_BMAP_RADIX;
while (lo + 1 < hi) {
mid = (lo + hi) >> 1;
if ((mask >> mid) != 0)
lo = mid;
else
hi = mid;
}
return (lo);
}
} }
/* /*
Context not available.
#endif #endif
struct gap_stats {
int num; /* number of gaps observed */
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
alcUnsubmitted
Not Done
Inline Actions

If every other block is allocated, this field can overflow.

alc: If every other block is allocated, this field can overflow.
daddr_t max; /* largest gap size */
daddr_t avg; /* average gap size */
daddr_t err; /* sum - num * avg */
int histo[127]; /* counts for gaps of various sizes */
int max_bucket;
u_daddr_t start;
};
alcUnsubmitted
Not Done
Inline Actions

Incorrect indentation.

alc: Incorrect indentation.
/*
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
* gap_stats_counting() - is the state 'counting 1 bits'?
* or 'skipping 0 bits'?
*/
static inline int
gap_stats_counting(struct gap_stats *stats)
{
alcUnsubmitted
Not Done
Inline Actions

Insert blank line.

alc: Insert blank line.
return (stats->start != -1);
alcUnsubmitted
Not Done
Inline Actions

Insert a blank line before the bzero().

alc: Insert a blank line before the bzero().
}
/*
* init_gap_stats() - initialize stats on gap sizes
*/
alcUnsubmitted
Done
Inline Actions

It is probably better to bzero() the entire structure and then initialize "start".

alc: It is probably better to bzero() the entire structure and then initialize "start".
static inline void
init_gap_stats(struct gap_stats *stats)
alcUnsubmitted
Done
Inline Actions

Insert blank line.

alc: Insert blank line.
{
bzero(stats, sizeof(*stats));
stats->start = -1;
}
/*
* update_gap_stats() - update stats on gap sizes
alcUnsubmitted
Done
Inline Actions

The u_daddr_t definition should come first because it is a larger data type.

alc: The u_daddr_t definition should come first because it is a larger data type.
*/
static void
update_gap_stats(struct gap_stats *stats, u_daddr_t posn)
{
u_daddr_t size;
int id, logsize;
if (!gap_stats_counting(stats)) {
stats->start = posn;
return;
}
size = posn - stats->start;
stats->start = -1;
if (size > stats->max)
alcUnsubmitted
Not Done
Inline Actions

This will probably need to change, but it can wait for a future revision.

alc: This will probably need to change, but it can wait for a future revision.
stats->max = size;
if (size == 1) {
id = 0;
alcUnsubmitted
Done
Inline Actions

Use postfix instead.

alc: Use postfix instead.
} else {
logsize = 1;
while ((size >> logsize) > 1)
logsize++;
id = 2 * logsize - 1;
if (size >> (logsize - 1) >= 3)
alcUnsubmitted
Done
Inline Actions

Use postfix.

alc: Use postfix.
id++;
}
stats->histo[id]++;
if (id > stats->max_bucket)
stats->max_bucket = id;
stats->err += (daddr_t)size - stats->avg;
stats->num++;
stats->avg += stats->err / stats->num;
stats->err %= stats->num;
}
alcUnsubmitted
Done
Inline Actions

Insert blank line.

alc: Insert blank line.
alcUnsubmitted
Not Done
Inline Actions

You need to use "%ju" and uintmax_t.

alc: You need to use "%ju" and uintmax_t.
/*
* dump_stats() - print stats on gap sizes
*/
static inline void
dump_gap_stats(struct sbuf *s, struct gap_stats *stats)
{
int i, val;
sbuf_printf(s, "number of gaps: %d\n", stats->num);
alcUnsubmitted
Done
Inline Actions

The outermost parens around the expression are not needed. Spaces are required around binary operators.

alc: The outermost parens around the expression are not needed. Spaces are required around binary…
sbuf_printf(s, "largest gap: %jd\n", (intmax_t)stats->max);
sbuf_printf(s, "average gap size: %jd\n", (intmax_t)stats->avg);
sbuf_printf(s, "histogram:\n");
for (i = 0; i <= stats->max_bucket; i++) {
val = (i == 0) ? 1 : ((3 - i % 2) << ((i - 1) / 2));
sbuf_printf(s, "%d\t%d\n", val, stats->histo[i]);
}
}
/*
* blist_stats() - dump radix tree stats
alcUnsubmitted
Not Done
Inline Actions

This needs to be declared in blist.h.

alc: This needs to be declared in blist.h.
*/
void
blist_stats(struct sbuf *s, blist_t bl)
{
alcUnsubmitted
Done
Inline Actions

The struct should come first.

alc: The struct should come first.
daddr_t bit, diff, i, nodes, radix;
u_daddr_t mask;
struct gap_stats stats;
init_gap_stats(&stats);
nodes = 0;
i = bl->bl_radix;
while (i < bl->bl_radix + bl->bl_blocks) {
radix = BLIST_BMAP_RADIX;
while (((i / radix) & BLIST_META_MASK) == 0) {
/*
* Skip meta node.
*/
radix *= BLIST_META_RADIX;
}
while (radix > BLIST_BMAP_RADIX) {
if (bl->bl_root[nodes].u.bmu_avail == 0) {
if (gap_stats_counting(&stats))
update_gap_stats(&stats, i);
break;
}
if (bl->bl_root[nodes].u.bmu_avail == radix) {
if (!gap_stats_counting(&stats))
update_gap_stats(&stats, i);
break;
}
nodes++;
radix /= BLIST_META_RADIX;
}
if (radix == BLIST_BMAP_RADIX) {
/*
* Scan leaf.
*/
mask = bl->bl_root[nodes].u.bmu_bitmap;
diff = mask ^ (mask << 1);
diff ^= gap_stats_counting(&stats);
while (diff) {
bit = diff & -diff;
update_gap_stats(&stats, i + bitpos(bit));
diff ^= bit;
}
}
nodes += radix_to_skip(radix);
i += radix;
}
update_gap_stats(&stats, i);
dump_gap_stats(s, &stats);
}
/************************************************************************ /************************************************************************
* ALLOCATION SUPPORT FUNCTIONS * * ALLOCATION SUPPORT FUNCTIONS *
************************************************************************ ************************************************************************
alcUnsubmitted
Not Done
Inline Actions

This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy(), or swp_pager_freeswapspace().

alc: This needs to be implemented in swap_pager.c. See swp_pager_getswapspace(), swp_pager_strategy…
Context not available.
* *
* This is the core of the allocator and is optimized for the * This is the core of the allocator and is optimized for the
* BLIST_BMAP_RADIX block allocation case. Otherwise, execution * BLIST_BMAP_RADIX block allocation case. Otherwise, execution
* time is proportional to log2(count) + log2(BLIST_BMAP_RADIX). * time is proportional to log2(count) + bitpos time.
*/ */
static daddr_t static daddr_t
blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor) blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor)
{ {
u_daddr_t mask; u_daddr_t mask;
int count1, hi, lo, mid, num_shifts, range1, range_ext; int count1, lo, num_shifts, range1, range_ext;
if (count == BLIST_BMAP_RADIX) { if (count == BLIST_BMAP_RADIX) {
/* /*
Context not available.
/* /*
* The least significant set bit in mask marks the start of the first * The least significant set bit in mask marks the start of the first
* available range of sufficient size. Clear all the bits but that one, * available range of sufficient size. Clear all the bits but that one,
* and then perform a binary search to find its position. * and then find its position.
*/ */
mask &= -mask; mask &= -mask;
hi = BLIST_BMAP_RADIX - count1; lo = bitpos(mask);
while (lo + 1 < hi) {
mid = (lo + hi) >> 1;
if ((mask >> mid) != 0)
lo = mid;
else
hi = mid;
}
/* /*
* Set in mask exactly the bits being allocated, and clear them from * Set in mask exactly the bits being allocated, and clear them from
Context not available.
int size = 1024; int size = 1024;
int i; int i;
blist_t bl; blist_t bl;
struct sbuf *s;
for (i = 1; i < ac; ++i) { for (i = 1; i < ac; ++i) {
const char *ptr = av[i]; const char *ptr = av[i];
Context not available.
case 'p': case 'p':
blist_print(bl); blist_print(bl);
break; break;
case 's':
s = sbuf_new_auto();
blist_stats(s, bl);
sbuf_finish(s);
printf("%s", sbuf_data(s));
sbuf_delete(s);
break;
case 'a': case 'a':
if (sscanf(buf + 1, "%lld", &count) == 1) { if (sscanf(buf + 1, "%lld", &count) == 1) {
daddr_t blk = blist_alloc(bl, count); daddr_t blk = blist_alloc(bl, count);
Context not available.
case 'h': case 'h':
puts( puts(
"p -print\n" "p -print\n"
"s -stats\n"
"a %d -allocate\n" "a %d -allocate\n"
"f %x %d -free\n" "f %x %d -free\n"
"l %x %d -fill\n" "l %x %d -fill\n"
Context not available.
View Options

sys/sys/ptrace.h

Loading...