8000 minix/minix/servers/mib/tree.c at master · ze-gois/minix · GitHub
[go: up one dir, main page]

Skip to content

Latest commit

 

History

History
1842 lines (1579 loc) · 53.4 KB

tree.c

File metadata and controls

1842 lines (1579 loc) · 53.4 KB
* ascending identifier order, so we must find the right place at which
* to insert the new node.
*
* For finding a free identifier, choose an ID that falls (well)
* outside the static range, both to avoid accidental retrieval by an
* application that uses a static ID, and to simplify verifying that
* the ID is indeed free. The sorting of dynamic nodes by identifier
* ensures that searching for a free identifier is O(n).
*
* At this time, we do not support some NetBSD features. We do not
* force success if the new node is sufficiently like an existing one.
* Also, we do not use global autoincrement for dynamic identifiers,
* although that could easily be changed.
*/
/* First check the static node array, just for collisions. */
for (id = 0; IS_STATIC_ID(parent, id); id++) {
node = &parent->node_scptr[id];
if (node->node_flags == 0)
continue;
if (id == given_id || !strcmp(name, node->node_name)) {
*idp = id;
*nodep = node;
return EEXIST;
}
}
/*
* Then try to find the place to insert a new dynamic node. At the
* same time, check for both identifier and name collisions.
*/
if (given_id >= 0)
id = given_id;
else
id = MAX(CREATE_BASE, parent->node_size);
for (prevp = &parent->node_dcptr; *prevp != NULL;
prevp = &((*prevp)->dynode_next)) {
if ((*prevp)->dynode_id > id)
break;
if ((*prevp)->dynode_id == id) {
if (given_id >= 0) {
*idp = id;
*nodep = &(*prevp)->dynode_node;
return EEXIST;
} else
id++;
}
if (!strcmp(name, (*prevp)->dynode_node.node_name)) {
*idp = (*prevp)->dynode_id;
*nodep = &(*prevp)->dynode_node;
return EEXIST;
}
}
/* Finally, check the rest of the dynamic nodes for name collisions. */
for (dynp = prevp; *dynp != NULL; dynp = &((*dynp)->dynode_next)) {
assert((*dynp)->dynode_id > id);
if (!strcmp(name, (*dynp)->dynode_node.node_name)) {
*idp = (*dynp)->dynode_id;
*nodep = &(*dynp)->dynode_node;
return EEXIST;
}
}
*idp = id;
*prevpp = prevp;
return OK;
}
/*
* Copy in a string from the user process, located at the given remote address,
* into the given local buffer. If no buffer is given, just compute the length
* of the string. On success, return OK. If 'sizep' is not NULL, it will be
* filled with the string size, including the null terminator. If a non-NULL
* buffer was given, the string will be copied into the provided buffer (also
* including null terminator). Return an error code on failure, which includes
* the case that no null terminator was found within the range of bytes that
* would fit in the given buffer.
*/
static int
mib_copyin_str(struct mib_newp * __restrict newp, vir_bytes addr,
char * __restrict buf, size_t bufsize, size_t * __restrict sizep)
{
char *ptr, *endp;
size_t chunk, len;
int r;
assert(newp != NULL);
assert(bufsize <= SSIZE_MAX);
if (addr == 0)
return EINVAL;
/*
* NetBSD has a kernel routine for copying in a string from userland.
* MINIX3 does not, since its system call interface has always relied
* on userland passing in string lengths. The sysctl(2) API does not
* provide the string length, and thus, we have to do a bit of guess
* work. If we copy too little at once, performance suffers. If we
* copy too much at once, we may trigger an unneeded page fault. Make
* use of page boundaries to strike a balance between those two. If we
* are requested to just get the string length, use the scratch buffer.
*/
len = 0;
while (bufsize > 0) {
chunk = PAGE_SIZE - (addr % PAGE_SIZE);
if (chunk > bufsize)
chunk = bufsize;
ptr = (buf != NULL) ? &buf[len] : scratch;
if ((r = mib_copyin_aux(newp, addr, ptr, chunk)) != OK)
return r;
if ((endp = memchr(ptr, '\0', chunk)) != NULL) {
/* A null terminator was found - success. */
if (sizep != NULL)
*sizep = len + (size_t)(endp - ptr) + 1;
return OK;
}
addr += chunk;
len += chunk;
bufsize -= chunk;
}
/* No null terminator found. */
return EINVAL;
}
/*
* Increase the version of the root node, and copy this new version to all
* nodes on the path to the given node, including that node itself.
*/
static void
mib_upgrade(struct mib_node * node)
{
uint32_t ver;
assert(node != NULL);
/*
* The root node determines the version of the entire tree. Do not use
* version number 0, as a zero version number indicates no interest in
* versions elsewhere.
*/
ver = mib_root.node_ver + 1;
if (ver == 0)
ver = 1;
/* Copy the new version to all the nodes on the path. */
do {
node->node_ver = ver;
node = node->node_parent;
} while (node != NULL);
}
/*
* Add a new dynamically allocated node into the tree, inserting it into the
* linked-list position of the parent tree as given by 'prevp'. Also update
* versions and counters accordingly. This function never fails.
*/
static void
mib_add(struct mib_dynode * dynode, struct mib_dynode ** prevp)
{
struct mib_node *parent;
parent = dynode->dynode_node.node_parent;
assert(parent != NULL);
/* Link the dynamic node into the list, in the right place. */
assert(prevp != NULL);
dynode->dynode_next = *prevp;
*prevp = dynode;
/* The parent node now has one more child. */
parent->node_csize++;
parent->node_clen++;
/* There is now one more node in the tree. */
mib_nodes++;
/*
* Bump the version of all nodes on the path to the new node, including
* the node itself.
*/
mib_upgrade(&dynode->dynode_node);
}
/*
* Create a node.
*/
static ssize_t
mib_create(struct mib_call * call, struct mib_node * parent,
struct mib_oldp * oldp, struct mib_newp * newp)
{
struct mib_dynode *dynode, **prevp;
struct mib_node *node;
struct sysctlnode scn;
size_t namelen, size;
ssize_t len;
bool b;
char c;
int r, id;
/* This is a privileged operation. */
if (!mib_authed(call))
return EPERM;
/*
* The parent must not be a remote node, but this is already implied by
* the fact that we got here at all.
*/
assert(SYSCTL_TYPE(parent->node_flags) == CTLTYPE_NODE);
assert(!(parent->node_flags & CTLFLAG_REMOTE));
/* The parent node must not be marked as read-only. */
if (!(parent->node_flags & CTLFLAG_READWRITE))
return EPERM;
/*
* Has the parent reached its child node limit? This check is entirely
* theoretical as long as we support only 32-bit virtual memory.
*/
if (parent->node_csize == INT_MAX)
return EINVAL;
assert(parent->node_clen <= parent->node_csize);
/* The caller must supply information on the child node to create. */
if (newp == NULL)
return EINVAL;
if ((r = mib_copyin(newp, &scn, sizeof(scn))) != OK)
return r;
/*
* We perform as many checks as possible before we start allocating
* memory. Then again, after allocation, copying in data may still
* fail. Unlike when setting values, we do not first copy data into a
* temporary buffer here, because we do not need to: if the copy fails,
* the entire create operation fails, so atomicity is not an issue.
*/
if (SYSCTL_VERS(scn.sysctl_flags) != SYSCTL_VERSION)
return EINVAL;
/*
* If a node version number is given, it must match the version of
* either the parent or the root node. The given version number is
* *not* used for the node being created.
*/
if (scn.sysctl_ver != 0 && scn.sysctl_ver != mib_root.node_ver &&
scn.sysctl_ver != parent->node_ver)
return EINVAL;
/*
* Validate the node flags. In addition to the NetBSD-allowed flags,
* we also allow UNSIGNED, and leave its interpretation to userland.
*/
if (SYSCTL_FLAGS(scn.sysctl_flags) &
~(SYSCTL_USERFLAGS | CTLFLAG_UNSIGNED))
return EINVAL;
if (!(scn.sysctl_flags & CTLFLAG_IMMEDIATE)) {
/*
* Without either IMMEDIATE or OWNDATA, data pointers are
* actually kernel addresses--a concept we do not support.
* Otherwise, if IMMEDIATE is not set, we are going to have to
* allocate extra memory for the data, so force OWNDATA to be.
* set. Node-type nodes have no data, though.
*/
if (SYSCTL_TYPE(scn.sysctl_flags) != CTLTYPE_NODE) {
if (!(scn.sysctl_flags & CTLFLAG_OWNDATA) &&
scn.sysctl_data != NULL)
return EINVAL; /* not meaningful on MINIX3 */
scn.sysctl_flags |= CTLFLAG_OWNDATA;
}
} else if (scn.sysctl_flags & CTLFLAG_OWNDATA)
return EINVAL;
/* The READWRITE flag consists of multiple bits. Sanitize. */
if (scn.sysctl_flags & CTLFLAG_READWRITE)
scn.sysctl_flags |= CTLFLAG_READWRITE;
/* Validate the node type and size, and do some additional checks. */
switch (SYSCTL_TYPE(scn.sysctl_flags)) {
case CTLTYPE_BOOL:
if (scn.sysctl_size != sizeof(bool))
return EINVAL;
break;
case CTLTYPE_INT:
if (scn.sysctl_size != sizeof(int))
return EINVAL;
break;
case CTLTYPE_QUAD:
if (scn.sysctl_size != sizeof(u_quad_t))
return EINVAL;
break;
case CTLTYPE_STRING:
/*
* For strings, a zero length means that we are supposed to
* allocate a buffer size based on the given string size.
*/
if (scn.sysctl_size == 0 && scn.sysctl_data != NULL) {
if ((r = mib_copyin_str(newp,
(vir_bytes)scn.sysctl_data, NULL, SSIZE_MAX,
&size)) != OK)
return r;
scn.sysctl_size = size;
}
/* FALLTHROUGH */
case CTLTYPE_STRUCT:
/*
* We do not set an upper size on the data size, since it would
* still be possible to create a large number of nodes, and
* this is a privileged operation ayway.
*/
if (scn.sysctl_size == 0 || scn.sysctl_size > SSIZE_MAX)
return EINVAL;
if (scn.sysctl_flags & CTLFLAG_IMMEDIATE)
return EINVAL;
break;
case CTLTYPE_NODE:
/*
* The zero size is an API requirement, but we also rely on the
* zero value internally, as the node has no static children.
*/
if (scn.sysctl_size != 0)
return EINVAL;
if (scn.sysctl_flags & (CTLFLAG_IMMEDIATE | CTLFLAG_OWNDATA))
return EINVAL;
if (scn.sysctl_csize != 0 || scn.sysctl_clen != 0 ||
scn.sysctl_child != NULL)
return EINVAL;
break;
default:
return EINVAL;
}
if (scn.sysctl_func != NULL || scn.sysctl_parent != NULL)
return EINVAL;
/* Verify that the given name is valid, and get its string length. */
namelen = mib_check_name(scn.sysctl_name, sizeof(scn.sysctl_name));
if (namelen == 0)
return EINVAL;
/*
* Find a free identifier, or check for ID collisions if a specific
* identifier was given. At the same time, scan for name collisions,
* and find the location at which to insert the new node in the list.
*/
r = mib_scan(parent, scn.sysctl_num, scn.sysctl_name, &id, &prevp,
&node);
if (r != OK) {
/*
* On collisions, if requested, copy out the existing node.
* This does not quite fit the general interaction model, as
* the service must now return a nonzero old length from a call
* that actually failed (in contrast to ENOMEM failures).
*/
if (r == EEXIST && oldp != NULL) {
len = mib_copyout_node(call, oldp, 0, id, node);
if (len > 0)
mib_setoldlen(call, len);
}
return r;
}
/*
* All checks so far have passed. "id" now contains the new node
* identifier, and "prevp" points to the pointer at which to insert the
* new node in its parent's linked list of dynamic nodes.
*
* We can now attempt to create and initialize a new dynamic node.
* Allocating nodes this way may cause heavy memory fragmentation over
* time, but we do not expect the tree to see heavy modification at run
* time, and the superuser has easier ways to get the MIB service in
* trouble. We note that even in low-memory conditions, the MIB
* service is always able to provide basic functionality.
*/
size = sizeof(*dynode) + namelen;
if (!(scn.sysctl_flags & CTLFLAG_IMMEDIATE))
size += scn.sysctl_size;
if ((dynode = malloc(size)) == NULL)
return EINVAL; /* do not return ENOMEM */
mib_objects++;
/* From here on, we have to free "dynode" before returning an error. */
r = OK;
memset(dynode, 0, sizeof(*dynode)); /* no need to zero all of "size" */
dynode->dynode_id = id;
strlcpy(dynode->dynode_name, scn.sysctl_name, namelen + 1);
node = &dynode->dynode_node;
node->node_flags = scn.sysctl_flags & ~SYSCTL_VERS_MASK;
if (SYSCTL_TYPE(scn.sysctl_flags) == CTLTYPE_NODE)
node->node_flags |= CTLFLAG_PARENT;
node->node_size = scn.sysctl_size;
node->node_parent = parent;
node->node_name = dynode->dynode_name;
/* Initialize the node value. */
if (scn.sysctl_flags & CTLFLAG_IMMEDIATE) {
switch (SYSCTL_TYPE(scn.sysctl_flags)) {
case CTLTYPE_BOOL:
/* Sanitize booleans. See the C99 _Bool comment. */
memcpy(&c, &scn.sysctl_bdata, sizeof(c));
node->node_bool = (bool)c;
break;
case CTLTYPE_INT:
node->node_int = scn.sysctl_idata;
break;
case CTLTYPE_QUAD:
node->node_quad = scn.sysctl_qdata;
break;
default:
assert(0);
}
} else if (SYSCTL_TYPE(scn.sysctl_flags) != CTLTYPE_NODE) {
node->node_data = dynode->dynode_name + namelen + 1;
/* Did the user supply initial data? If not, use zeroes. */
if (scn.sysctl_data != NULL) {
/*
* For strings, do not copy in more than needed. This
* is just a nice feature which allows initialization
* of large string buffers with short strings.
*/
if (SYSCTL_TYPE(scn.sysctl_flags) == CTLTYPE_STRING)
r = mib_copyin_str(newp,
(vir_bytes)scn.sysctl_data,
node->node_data, scn.sysctl_size, NULL);
else
r = mib_copyin_aux(newp,
(vir_bytes)scn.sysctl_data,
node->node_data, scn.sysctl_size);
} else
memset(node->node_data, 0, scn.sysctl_size);
/*
* Sanitize booleans. See the C99 _Bool comment elsewhere.
* In this case it is not as big of a deal, as we will not be
* accessing the boolean value directly ourselves.
*/
if (r == OK && SYSCTL_TYPE(scn.sysctl_flags) == CTLTYPE_BOOL) {
b = (bool)*(char *)node->node_data;
memcpy(node->node_data, &b, sizeof(b));
}
}
/*
* Even though it would be entirely possible to set a description right
* away as well, this does not seem to be supported on NetBSD at all.
*/
/* Deal with earlier failures now. */
if (r != OK) {
free(dynode);
mib_objects--;
return r;
}
/*
* At this point, actual creation can no longer fail. Add the node
* into the tree, and update versions and counters.
*/
mib_add(dynode, prevp);
/*
* Copy out the newly created node as resulting ("old") data. Do not
* undo the creation if this fails, though.
*/
return mib_copyout_node(call, oldp, 0, id, node);
}
/*
* Remove the given node from the tree. If 'prevp' is NULL, the node is a
* static node which should be zeroed out. If 'prevp' is not NULL, the node is
* a dynamic node which should be freed; 'prevp' will then point to the pointer
* to its dynode container. Also update versions and counters as appropriate.
* This function never fails.
*/
static void
mib_remove(struct mib_node * node, struct mib_dynode ** prevp)
{
struct mib_dynode *dynode;
struct mib_node *parent;
parent = node->node_parent;
assert(parent != NULL);
/* If the description was allocated, free it. */
if (node->node_flags & CTLFLAG_OWNDESC) {
free(__UNCONST(node->node_desc));
mib_objects--;
}
/*
* Static nodes only use static memory, and dynamic nodes have the data
* area embedded in the dynode object. In neither case is data memory
* allocated separately, and thus, it need never be freed separately.
* Therefore we *must not* check CTLFLAG_OWNDATA here.
*/
assert(parent->node_csize > 0);
assert(parent->node_clen > 0);
/*
* Dynamic nodes must be freed. Freeing the dynode object also frees
* the node name and any associated data. Static nodes are zeroed out,
* and the static memory they referenced will become inaccessible.
*/
if (prevp != NULL) {
dynode = *prevp;
*prevp = dynode->dynode_next;
assert(node == &dynode->dynode_node);
free(dynode);
mib_objects--;
parent->node_csize--;
} else
memset(node, 0, sizeof(*node));
parent->node_clen--;
mib_nodes--;
/* Bump the version of all n D4D9 odes on the path to the destroyed node. */
mib_upgrade(parent);
}
/*
* Destroy a node.
*/
static ssize_t
mib_destroy(struct mib_call * call, struct mib_node * parent,
struct mib_oldp * oldp, struct mib_newp * newp)
{
struct mib_dynode **prevp;
struct mib_node *node;
struct sysctlnode scn;
ssize_t r;
/* This is a privileged operation. */
if (!mib_authed(call))
return EPERM;
/* The parent node must not be marked as read-only. */
if (!(parent->node_flags & CTLFLAG_READWRITE))
return EPERM;
/* The caller must specify which child node to destroy. */
if (newp == NULL)
return EINVAL;
if ((r = mib_copyin(newp, &scn, sizeof(scn))) != OK)
return r;
if (SYSCTL_VERS(scn.sysctl_flags) != SYSCTL_VERSION)
return EINVAL;
/* Locate the child node. */
if ((node = mib_find(parent, scn.sysctl_num, &prevp)) == NULL)
return ENOENT;
/* The node must not be marked as permanent. */
if (node->node_flags & CTLFLAG_PERMANENT)
return EPERM;
/* For node-type nodes, extra rules apply. */
if (SYSCTL_TYPE(node->node_flags) == CTLTYPE_NODE) {
/* The node must not be a mount point. */
if (node->node_flags & CTLFLAG_REMOTE)
return EBUSY;
/* The node must not have an associated function. */
if (!(node->node_flags & CTLFLAG_PARENT))
return EPERM;
/* The target node must itself not have child nodes. */
if (node->node_clen != 0)
return ENOTEMPTY;
}
/* If the user supplied a version, it must match the node version. */
if (scn.sysctl_ver != 0 && scn.sysctl_ver != node->node_ver)
return EINVAL; /* NetBSD inconsistently throws ENOENT here */
/* If the user supplied a name, it must match the node name. */
if (scn.sysctl_name[0] != '\0') {
if (memchr(scn.sysctl_name, '\0',
sizeof(scn.sysctl_name)) == NULL)
return EINVAL;
if (strcmp(scn.sysctl_name, node->node_name))
return EINVAL; /* also ENOENT on NetBSD */
}
/*
* Copy out the old node if requested, otherwise return the length
* anyway. The node will be destroyed even if this call fails,
* because that is how NetBSD behaves.
*/
r = mib_copyout_node(call, oldp, 0, scn.sysctl_num, node);
/*
* Remove the node from the tree. The procedure depends on whether the
* node is static (prevp == NULL) or dynamic (prevp != NULL). Also
* update versions and counters.
*/
mib_remove(node, prevp);
return r;
}
/*
* Copy out a node description to userland, using the exchange format for node
* descriptions (namely, a sysctldesc structure). Return the size of the
* object that is (or, if the description falls outside the requested data
* range, would be) copied out on success, or a negative error code on failure.
* The function may return 0 to indicate that nothing was copied out after all.
*/
static ssize_t
mib_copyout_desc(struct mib_call * call, struct mib_oldp * oldp, size_t off,
int id, const struct mib_node * node)
{
struct sysctldesc *scd;
size_t size;
int r;
/* Descriptions of private nodes are considered private too. */
if ((node->node_flags & CTLFLAG_PRIVATE) && !mib_authed(call))
return 0;
/* The description length includes the null terminator. */
if (node->node_desc != NULL)
size = strlen(node->node_desc) + 1;
else
size = 1;
assert(sizeof(*scd) + size <= sizeof(scratch));
scd = (struct sysctldesc *)scratch;
memset(scd, 0, sizeof(*scd));
scd->descr_num = id;
scd->descr_ver = node->node_ver;
scd->descr_len = size;
if (node->node_desc != NULL)
strlcpy(scd->descr_str, node->node_desc,
sizeof(scratch) - sizeof(*scd));
else
scd->descr_str[0] = '\0';
size += offsetof(struct sysctldesc, descr_str);
if ((r = mib_copyout(oldp, off, scratch, size)) < 0)
return r;
/*
* By aligning just the size, we may leave garbage between the entries
* copied out, which is fine because it is userland's own data.
*/
return roundup2(size, sizeof(int32_t));
}
/*
* Retrieve node descriptions in bulk, or retrieve or assign a particular
* node's description.
*/
static ssize_t
mib_describe(struct mib_call * call, struct mib_node * parent,
struct mib_oldp * oldp, struct mib_newp * newp)
{
struct sysctlnode scn;
struct mib_node *node;
struct mib_dynode *dynode;
size_t off;
int r, id;
/* If new data are given, they identify a particular target node. */
if (newp != NULL) {
if ((r = mib_copyin(newp, &scn, sizeof(scn))) != OK)
return r;
if (SYSCTL_VERS(scn.sysctl_flags) != SYSCTL_VERSION)
return EINVAL;
/* Locate the child node. */
if ((node = mib_find(parent, scn.sysctl_num, NULL)) == NULL)
return ENOENT;
/* Descriptions of private nodes are considered private too. */
if ((node->node_flags & CTLFLAG_PRIVATE) && !mib_authed(call))
return EPERM;
/*
* If a description pointer was given, this is a request to
* set the node's description.
0