X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flib%2Flib.c;h=91fb318f2c8ebaf5898019c32f1b802e1d429147;hb=f6580e9ad405b519dbe85027691bf3c66074b0a4;hp=6e676cd1a6b1c9e04e356d08b83c23d18910c63c;hpb=aec1ddcd754c778a713b8cd5593c0a304db9d50b;p=pintos-anon diff --git a/src/lib/lib.c b/src/lib/lib.c index 6e676cd..91fb318 100644 --- a/src/lib/lib.c +++ b/src/lib/lib.c @@ -1,13 +1,20 @@ +#include "lib.h" #include #include #include #include #include "debug.h" -#include "interrupt.h" -#include "lib.h" -#include "serial.h" -#include "vga.h" +#include "devices/serial.h" +#include "devices/vga.h" +#include "threads/interrupt.h" + +static void +vprintf_core (const char *format, va_list args, + void (*output) (char, void *), void *aux); + +/* */ +/* Sets the SIZE bytes in DST to VALUE. */ void * memset (void *dst_, int value, size_t size) { @@ -21,6 +28,8 @@ memset (void *dst_, int value, size_t size) return dst_; } +/* Copies SIZE bytes from SRC to DST, which must not overlap. + Returns DST. */ void * memcpy (void *dst_, const void *src_, size_t size) { @@ -36,6 +45,8 @@ memcpy (void *dst_, const void *src_, size_t size) return dst_; } +/* Copies SIZE bytes from SRC to DST, which are allowed to + overlap. Returns DST. */ void * memmove (void *dst_, const void *src_, size_t size) { @@ -61,6 +72,9 @@ memmove (void *dst_, const void *src_, size_t size) return dst; } +/* Returns a pointer to the first occurrence of CH in the first + SIZE bytes starting at BLOCK. Returns a null pointer if CH + does not occur in BLOCK. */ void * memchr (const void *block_, int ch_, size_t size) { @@ -76,6 +90,10 @@ memchr (const void *block_, int ch_, size_t size) return NULL; } +/* Find the first differing byte in the two blocks of SIZE bytes + at A and B. Returns a positive value if the byte in A is + greater, a negative value if the byte in B is greater, or zero + if blocks A and B are equal. */ int memcmp (const void *a_, const void *b_, size_t size) { @@ -91,6 +109,35 @@ memcmp (const void *a_, const void *b_, size_t size) return 0; } +/* Finds and returns the first occurrence of C in STRING, or a + null pointer if C does not appear in STRING. If C == '\0' + then returns a pointer to the null terminator at the end of + STRING. */ +char * +strchr (const char *string, int c_) +{ + char c = c_; + + ASSERT (string != NULL); + + for (;;) + if (*string == c) + return (char *) string; + else if (*string == '\0') + return NULL; + else + string++; +} + +/* Copies string SRC to DST. If SRC is longer than SIZE - 1 + characters, only SIZE - 1 characters are copied. A null + terminator is always written to DST, unless SIZE is 0. + Returns the length of SRC. + + strlcpy() is not in the standard C library, but it is an + increasingly popular extension. See + http://www.courtesan.com/todd/papers/strlcpy.html for + information on strlcpy(). */ size_t strlcpy (char *dst, const char *src, size_t size) { @@ -102,14 +149,16 @@ strlcpy (char *dst, const char *src, size_t size) src_len = strlen (src); if (size > 0) { - size_t dst_len_max = size - 1; - size_t dst_len = src_len < dst_len_max ? src_len : dst_len_max; + size_t dst_len = size - 1; + if (src_len < dst_len) + src_len = dst_len; memcpy (dst, src, dst_len); dst[dst_len] = '\0'; } return src_len; } +/* Returns the length of STRING. */ size_t strlen (const char *string) { @@ -122,22 +171,23 @@ strlen (const char *string) return p - string; } -char * -strchr (const char *string, int c_) +/* If STRING is less than MAXLEN characters in length, returns + its actual length. Otherwise, returns MAXLEN. */ +size_t +strnlen (const char *string, size_t maxlen) { - char c = c_; + size_t length; - ASSERT (string != NULL); - - for (;;) - if (*string == c) - return (char *) string; - else if (*string == '\0') - return NULL; - else - string++; + for (length = 0; string[length] != '\0' && length < maxlen; length++) + continue; + return length; } +/* Finds the first differing characters in strings A and B. + Returns a positive value if the character in A (as an unsigned + char) is greater, a negative value if the character in B (as + an unsigned char) is greater, or zero if strings A and B are + equal. */ int strcmp (const char *a_, const char *b_) { @@ -156,6 +206,37 @@ strcmp (const char *a_, const char *b_) return *a < *b ? -1 : *a > *b; } +/* Breaks a string into tokens separated by DELIMITERS. The + first time this function is called, S should be the string to + tokenize, and in subsequent calls it must be a null pointer. + SAVE_PTR is the address of a `char *' variable used to keep + track of the tokenizer's position. The return value each time + is the next token in the string, or a null pointer if no + tokens remain. + + This function treats multiple adjacent delimiters as a single + delimiter. The returned tokens will never be length 0. + DELIMITERS may change from one call to the next within a + single string. + + strtok_r() modifies the string S, changing delimiters to null + bytes. Thus, S must be a modifiable string. + + Example usage: + + char s[] = " String to tokenize. "; + char *token, *save_ptr; + + for (token = strtok_r (s, " ", &save_ptr); token != NULL; + token = strtok_r (NULL, " ", &save_ptr)) + printf ("'%s'\n", token); + + outputs: + + 'String' + 'to' + 'tokenize.' +*/ char * strtok_r (char *s, const char *delimiters, char **save_ptr) { @@ -198,7 +279,11 @@ strtok_r (char *s, const char *delimiters, char **save_ptr) *save_ptr = s; return token; } + +/* */ +/* Converts a string representation of a signed decimal integer + in S into an `int', which is returned. */ int atoi (const char *s) { @@ -231,71 +316,63 @@ atoi (const char *s) return value; } -static void -vprintf_core (const char *format, va_list args, - void (*output) (char, void *), void *aux); - -static void -vprintk_helper (char ch, void *aux UNUSED) -{ - vga_putc (ch); - serial_outb (ch); -} +/* */ -void -vprintk (const char *format, va_list args) -{ - enum if_level old_level = intr_disable (); - vprintf_core (format, args, vprintk_helper, NULL); - intr_set_level (old_level); -} - -void -printk (const char *format, ...) -{ - va_list args; - - va_start (args, format); - vprintk (format, args); - va_end (args); -} - +/* Auxiliary data for vsnprintf_helper(). */ struct vsnprintf_aux { - char *p; - int length; - int max_length; + char *p; /* Current output position. */ + int length; /* Length of output string. */ + int max_length; /* Max length of output string. */ }; -static void -vsnprintf_helper (char ch, void *aux_) -{ - struct vsnprintf_aux *aux = aux_; - - if (aux->length++ < aux->max_length) - *aux->p++ = ch; -} +static void vsnprintf_helper (char, void *); +/* Like vprintf(), except that output is stored into BUFFER, + which must have space for BUF_SIZE characters. Writes at most + BUF_SIZE - 1 characters to BUFFER, followed by a null + terminator. BUFFER will always be null-terminated unless + BUF_SIZE is zero. Returns the number of characters that would + have been written to BUFFER, not including a null terminator, + had there been enough room. */ int -vsnprintf (char *buffer, size_t buf_size, - const char *format, va_list args) +vsnprintf (char *buffer, size_t buf_size, const char *format, va_list args) { + /* Set up aux data for vsnprintf_helper(). */ struct vsnprintf_aux aux; aux.p = buffer; aux.length = 0; aux.max_length = buf_size > 0 ? buf_size - 1 : 0; - + + /* Do most of the work. */ vprintf_core (format, args, vsnprintf_helper, &aux); + /* Add null terminator. */ if (buf_size > 0) *aux.p = '\0'; return aux.length; } +/* Helper function for vsnprintf(). */ +static void +vsnprintf_helper (char ch, void *aux_) +{ + struct vsnprintf_aux *aux = aux_; + + if (aux->length++ < aux->max_length) + *aux->p++ = ch; +} + +/* Like printf(), except that output is stored into BUFFER, + which must have space for BUF_SIZE characters. Writes at most + BUF_SIZE - 1 characters to BUFFER, followed by a null + terminator. BUFFER will always be null-terminated unless + BUF_SIZE is zero. Returns the number of characters that would + have been written to BUFFER, not including a null terminator, + had there been enough room. */ int -snprintf (char *buffer, size_t buf_size, - const char *format, ...) +snprintf (char *buffer, size_t buf_size, const char *format, ...) { va_list args; int retval; @@ -307,39 +384,283 @@ snprintf (char *buffer, size_t buf_size, return retval; } -/* printf() and friends internals. You do not need to understand - this code. */ +/* Nonstandard functions. */ + +static void vprintk_helper (char, void *); + +/* Like vprintf(), except that output is written to the system + console, which is defined as the video display and the first + serial port (at the same time). */ +void +vprintk (const char *format, va_list args) +{ + enum intr_level old_level = intr_disable (); + vprintf_core (format, args, vprintk_helper, NULL); + intr_set_level (old_level); +} +/* Helper function for vprintk(). */ +static void +vprintk_helper (char ch, void *aux UNUSED) +{ + vga_putc (ch); + serial_outb (ch); +} + +/* Like printf(), except that output is written to the system + console, which is defined as the video display and the first + serial port (at the same time). */ +void +printk (const char *format, ...) +{ + va_list args; + + va_start (args, format); + vprintk (format, args); + va_end (args); +} + +/* printf() formatting internals. */ + +/* A printf() conversion. */ struct printf_conversion { + /* Flags. */ enum { - MINUS = 1 << 0, - PLUS = 1 << 1, - SPACE = 1 << 2, - POUND = 1 << 3, - ZERO = 1 << 4, - GROUP = 1 << 5 + MINUS = 1 << 0, /* '-' */ + PLUS = 1 << 1, /* '+' */ + SPACE = 1 << 2, /* ' ' */ + POUND = 1 << 3, /* '#' */ + ZERO = 1 << 4, /* '0' */ + GROUP = 1 << 5 /* '\'' */ } flags; + /* Minimum field width. */ int width; + + /* Numeric precision. + -1 indicates no precision was specified. */ int precision; + /* Type of argument to format. */ enum { - CHAR = 1, - SHORT = 2, - INT = 3, - INTMAX = 4, - LONG = 5, - LONGLONG = 6, - PTRDIFFT = 7, - SIZET = 8 + CHAR = 1, /* hh */ + SHORT = 2, /* h */ + INT = 3, /* (none) */ + INTMAX = 4, /* j */ + LONG = 5, /* l */ + LONGLONG = 6, /* ll */ + PTRDIFFT = 7, /* t */ + SIZET = 8 /* z */ } type; }; +struct integer_base + { + int base; /* Base. */ + const char *digits; /* Collection of digits. */ + const char *signifier; /* Prefix used with # flag. */ + int group; /* Number of digits to group with ' flag. */ + }; + +static const struct integer_base base_d = {10, "0123456789", "", 3}; +static const struct integer_base base_o = {8, "01234567", "0", 3}; +static const struct integer_base base_x = {16, "0123456789abcdef", "0x", 4}; +static const struct integer_base base_X = {16, "0123456789ABCDEF", "0X", 4}; + +static const char *parse_conversion (const char *format, + struct printf_conversion *, + va_list *); +static void format_integer (uintmax_t value, bool negative, + const struct integer_base *, + const struct printf_conversion *, + void (*output) (char, void *), void *aux); +static void output_dup (char ch, size_t cnt, + void (*output) (char, void *), void *aux); +static void format_string (const char *string, size_t length, + struct printf_conversion *, + void (*output) (char, void *), void *aux); +static void printf_core (const char *format, + void (*output) (char, void *), void *aux, ...); + +static void +vprintf_core (const char *format, va_list args, + void (*output) (char, void *), void *aux) +{ + for (; *format != '\0'; format++) + { + struct printf_conversion c; + + /* Literally copy non-conversions to output. */ + if (*format != '%') + { + output (*format, aux); + continue; + } + format++; + + /* %% => %. */ + if (*format == '%') + { + output ('%', aux); + continue; + } + + /* Parse conversion specifiers. */ + format = parse_conversion (format, &c, &args); + + /* Do conversion. */ + switch (*format) + { + case 'd': + case 'i': + { + /* Signed integer conversions. */ + intmax_t value; + + switch (c.type) + { + case CHAR: + value = (signed char) va_arg (args, int); + break; + case SHORT: + value = (short) va_arg (args, int); + break; + case INT: + value = va_arg (args, int); + break; + case LONG: + value = va_arg (args, long); + break; + case LONGLONG: + value = va_arg (args, long long); + break; + case PTRDIFFT: + value = va_arg (args, ptrdiff_t); + break; + case SIZET: + value = va_arg (args, size_t); + break; + default: + NOT_REACHED (); + } + + format_integer (value < 0 ? -value : value, + value < 0, &base_d, &c, output, aux); + } + break; + + case 'o': + case 'u': + case 'x': + case 'X': + { + /* Unsigned integer conversions. */ + uintmax_t value; + const struct integer_base *b; + + switch (c.type) + { + case CHAR: + value = (unsigned char) va_arg (args, unsigned); + break; + case SHORT: + value = (unsigned short) va_arg (args, unsigned); + break; + case INT: + value = va_arg (args, unsigned); + break; + case LONG: + value = va_arg (args, unsigned long); + break; + case LONGLONG: + value = va_arg (args, unsigned long long); + break; + case PTRDIFFT: + value = va_arg (args, ptrdiff_t); + break; + case SIZET: + value = va_arg (args, size_t); + break; + default: + NOT_REACHED (); + } + + switch (*format) + { + case 'o': b = &base_o; break; + case 'u': b = &base_d; break; + case 'x': b = &base_x; break; + case 'X': b = &base_X; break; + default: NOT_REACHED (); + } + + format_integer (value, false, b, &c, output, aux); + } + break; + + case 'c': + { + /* Treat character as single-character string. */ + char ch = va_arg (args, int); + format_string (&ch, 1, &c, output, aux); + } + break; + + case 's': + { + /* String conversion. */ + const char *s = va_arg (args, char *); + if (s == NULL) + s = "(null)"; + + /* Limit string length according to precision. + Note: if c.precision == -1 then strnlen() will get + SIZE_MAX for MAXLEN, which is just what we want. */ + format_string (s, strnlen (s, c.precision), &c, output, aux); + } + break; + + case 'p': + { + /* Pointer conversion. + Format non-null pointers as %#x. */ + void *p = va_arg (args, void *); + + c.flags = POUND; + if (p != NULL) + format_integer ((uintptr_t) p, false, &base_x, &c, output, aux); + else + format_string ("(nil)", 5, &c, output, aux); + } + break; + + case 'f': + case 'e': + case 'E': + case 'g': + case 'G': + case 'n': + /* We don't support floating-point arithmetic, + and %n can be part of a security hole. */ + printf_core ("<>", output, aux, *format); + break; + + default: + printf_core ("<>", output, aux, *format); + break; + } + } +} + +/* Parses conversion option characters starting at FORMAT and + initializes C appropriately. Returns the character in FORMAT + that indicates the conversion (e.g. the `d' in `%d'). Uses + *ARGS for `*' field widths and precisions. */ static const char * parse_conversion (const char *format, struct printf_conversion *c, va_list *args) @@ -447,17 +768,11 @@ parse_conversion (const char *format, struct printf_conversion *c, c->type = LONG; break; - case 'L': - case 'q': - c->type = LONGLONG; - break; - case 't': c->type = PTRDIFFT; break; case 'z': - case 'Z': c->type = SIZET; break; @@ -469,25 +784,22 @@ parse_conversion (const char *format, struct printf_conversion *c, return format; } +/* Performs an integer conversion, writing output to OUTPUT with + auxiliary data AUX. The integer converted has absolute value + VALUE. If NEGATIVE is true the value is negative, otherwise + positive. The output will use the given DIGITS, with + strlen(DIGITS) indicating the output base. Details of the + conversion are in C. */ static void -output_dup (char ch, size_t cnt, void (*output) (char, void *), void *aux) -{ - while (cnt-- > 0) - output (ch, aux); -} - -static void -printf_integer (uintmax_t value, bool negative, const char *digits, - struct printf_conversion *c, +format_integer (uintmax_t value, bool negative, const struct integer_base *b, + const struct printf_conversion *c, void (*output) (char, void *), void *aux) - { - char buf[64], *cp; - int base; - const char *base_name; - int pad_cnt, group_cnt; - - base = strlen (digits); + char buf[64], *cp; /* Buffer and current position. */ + const char *signifier; /* b->signifier or "". */ + int precision; /* Rendered precision. */ + int pad_cnt; /* # of pad characters to fill field width. */ + int group_cnt; /* # of digits grouped so far. */ /* Accumulate digits into buffer. This algorithm produces digits in reverse order, so later we @@ -497,21 +809,22 @@ printf_integer (uintmax_t value, bool negative, const char *digits, group_cnt = 0; while (value > 0) { - if ((c->flags & GROUP) && group_cnt++ == 3) + if ((c->flags & GROUP) && group_cnt++ == b->group) { *cp++ = ','; group_cnt = 0; } - *cp++ = digits[value % base]; - value /= base; + *cp++ = b->digits[value % b->base]; + value /= b->base; } /* Append enough zeros to match precision. - If precision is 0, then a value of zero is rendered as a - null string. Otherwise at least one digit is presented. */ - if (c->precision < 0) - c->precision = 1; - while (cp - buf < c->precision && cp - buf < (int) sizeof buf - 8) + If requested precision is 0, then a value of zero is + rendered as a null string, otherwise as "0". */ + precision = c->precision < 0 ? 1 : c->precision; + if (precision < 0) + precision = 1; + while (cp - buf < precision && cp - buf < (int) sizeof buf - 8) *cp++ = '0'; /* Append sign. */ @@ -522,26 +835,17 @@ printf_integer (uintmax_t value, bool negative, const char *digits, else if (negative) *cp++ = '-'; - /* Get name of base. */ - base_name = ""; - if (c->flags & POUND) - { - if (base == 8) - base_name = "0"; - else if (base == 16) - base_name = digits[0xa] == 'a' ? "0x" : "0X"; - } - /* Calculate number of pad characters to fill field width. */ - pad_cnt = c->width - (cp - buf) - strlen (base_name); + signifier = c->flags & POUND ? b->signifier : ""; + pad_cnt = c->width - (cp - buf) - strlen (signifier); if (pad_cnt < 0) pad_cnt = 0; /* Do output. */ if ((c->flags & (MINUS | ZERO)) == 0) output_dup (' ', pad_cnt, output, aux); - while (*base_name != '\0') - output (*base_name++, aux); + while (*signifier != '\0') + output (*signifier++, aux); if (c->flags & ZERO) output_dup ('0', pad_cnt, output, aux); while (cp > buf) @@ -550,8 +854,19 @@ printf_integer (uintmax_t value, bool negative, const char *digits, output_dup (' ', pad_cnt, output, aux); } +/* Writes CH to OUTPUT with auxiliary data AUX, CNT times. */ static void -printf_string (const char *string, size_t length, +output_dup (char ch, size_t cnt, void (*output) (char, void *), void *aux) +{ + while (cnt-- > 0) + output (ch, aux); +} + +/* Formats the LENGTH characters starting at STRING according to + the conversion specified in C. Writes output to OUTPUT with + auxiliary data AUX. */ +static void +format_string (const char *string, size_t length, struct printf_conversion *c, void (*output) (char, void *), void *aux) { @@ -563,6 +878,8 @@ printf_string (const char *string, size_t length, output_dup (' ', c->width - 1, output, aux); } +/* Wrapper for vprintf_core() that converts varargs into a + va_list. */ static void printf_core (const char *format, void (*output) (char, void *), void *aux, ...) @@ -573,214 +890,29 @@ printf_core (const char *format, vprintf_core (format, args, output, aux); va_end (args); } - -static void -vprintf_core (const char *format, va_list args, - void (*output) (char, void *), void *aux) -{ - for (; *format != '\0'; format++) - { - struct printf_conversion c; - - /* Literally copy non-conversions to output. */ - if (*format != '%') - { - output (*format, aux); - continue; - } - format++; - - /* %% => %. */ - if (*format == '%') - { - output ('%', aux); - continue; - } - - format = parse_conversion (format, &c, &args); - switch (*format) - { - case 'd': - case 'i': - { - intmax_t value; - uintmax_t abs_value; - bool negative = false; - - switch (c.type) - { - case CHAR: - value = (signed char) va_arg (args, int); - break; - case SHORT: - value = (short) va_arg (args, int); - break; - case INT: - value = va_arg (args, int); - break; - case LONG: - value = va_arg (args, long); - break; - case LONGLONG: - value = va_arg (args, long long); - break; - case PTRDIFFT: - value = va_arg (args, ptrdiff_t); - break; - case SIZET: - value = va_arg (args, size_t); - break; - default: - NOT_REACHED (); - } - - if (value < 0) - { - negative = true; - abs_value = -value; - } - else - abs_value = value; - - printf_integer (abs_value, negative, "0123456789", - &c, output, aux); - } - break; - - case 'o': - case 'u': - case 'x': - case 'X': - { - uintmax_t value; - const char *digits; - - switch (c.type) - { - case CHAR: - value = (unsigned char) va_arg (args, unsigned); - break; - case SHORT: - value = (unsigned short) va_arg (args, unsigned); - break; - case INT: - value = va_arg (args, unsigned); - break; - case LONG: - value = va_arg (args, unsigned long); - break; - case LONGLONG: - value = va_arg (args, unsigned long long); - break; - case PTRDIFFT: - value = va_arg (args, ptrdiff_t); - break; - case SIZET: - value = va_arg (args, size_t); - break; - default: - NOT_REACHED (); - } - - switch (*format) - { - case 'o': - digits = "01234567"; - break; - case 'u': - digits = "0123456789"; - break; - case 'x': - digits = "0123456789abcdef"; - break; - case 'X': - digits = "0123456789ABCDEF"; - break; - default: - NOT_REACHED (); - } - - printf_integer (value, false, digits, &c, output, aux); - } - break; - - case 'c': - { - char ch = va_arg (args, int); - printf_string (&ch, 1, &c, output, aux); - } - break; - - case 's': - { - const char *s; - size_t length; - - s = va_arg (args, char *); - if (s == NULL) - s = "(null)"; - - if (c.precision >= 0) - { - const char *zero = memchr (s, '\0', c.precision); - if (zero != NULL) - length = zero - s; - else - length = c.precision; - } - else - length = strlen (s); - - printf_string (s, length, &c, output, aux); - } - break; - - case 'p': - { - void *p = va_arg (args, void *); - - c.flags = POUND; - if (p != NULL) - printf_integer ((uintptr_t) p, - false, "0123456789abcdef", &c, - output, aux); - else - printf_string ("(nil)", 5, &c, output, aux); - } - break; - - case 'f': - case 'e': - case 'E': - case 'g': - case 'G': - case 'n': - printf_core ("<>", output, aux, *format); - break; - - default: - printf_core ("<>", output, aux, *format); - break; - } - } -} +/* Dumps the SIZE bytes in BUFFER to the console as hex bytes + arranged 16 per line. If ASCII is true then the corresponding + ASCII characters are also rendered alongside. */ void hex_dump (const void *buffer, size_t size, bool ascii) { - const size_t n_per_line = 16; - const uint8_t *p = buffer; - size_t ofs = 0; + const size_t n_per_line = 16; /* Maximum bytes per line. */ + size_t n; /* Number of bytes in this line. */ + const uint8_t *p; /* Start of current line in buffer. */ - while (size > 0) + for (p = buffer; p < (uint8_t *) buffer + size; p += n) { - size_t n, i; + size_t i; - printk ("%08zx", ofs); - n = size >= n_per_line ? n_per_line : size; + /* Number of bytes on this line. */ + n = (uint8_t *) (buffer + size) - p; + if (n > n_per_line) + n = n_per_line; + + /* Print line. */ for (i = 0; i < n; i++) printk ("%c%02x", i == n_per_line / 2 ? '-' : ' ', (unsigned) p[i]); - if (ascii) { for (; i < n_per_line; i++) @@ -793,9 +925,5 @@ hex_dump (const void *buffer, size_t size, bool ascii) printk ("|"); } printk ("\n"); - - p += n; - ofs += n; - size -= n; } }