Project01 - String Library Implementation

[emuwang]

Implemented the following functions:

• char strncpy(char dst, const char *src, uint n);
• int strncmp(const char s1, const char s2, uint n);
• char strncat(char restrict s1, const char *restrict s2, uint n);
• char strstr(const char haystack, const char *needle);
• uint strspn(const char s, const char accept);
• uint strcspn(const char s, const char reject);
• char strtok(char restrict str, const char *restrict sep);
• char strtok_r(char restrict str, const char *restrict sep, char **restrict last);
• char *strsep(char *stringp, const char delim);
• int scanf(const char *restrict format, ...);

[sghahghahi]

I will code review this!

[atanaspatterson]

I'll also code review it!!

[atanaspatterson]

Hi all, here's my suggested changes/improvements:

• in scanf, I tested passing strings instead of integers, and they still got converted into integers leading to confusing output. For this, maybe comparing the input strings with the result given by atoi can help. Maybe even simpler logic could work, since I see that you pretty much show length 0, so you can maybe print something else if your length == 0. In addition, the second part did not seem to work well in most cases: scanf: Input two integers(space separated, can be negative): a b 0 0 0 Input three strings(space separated): hi hello hi 1 hi (null)

• Passing NULL to the string functions will break them. I tested passing it in strspn and strcat, both of which broke the code (used my own test cases file). Probably just handling NULL cases at the start of each function would solve this (like if str1 == NULL || str2 == NULL) { handle }

• -Testing strncat with null: Concatenated string: Hello, i�"�& (weird output) Testing strcspn with null: Span of characters: 10 (passed null - should not be 10

• For one more tiny thing, my compiler (for some reason) did not like strtok_r being called inside strtok before it was defined, so simply swapping the function definitions would do the trick(strtok_r before strtok).

The string functions look great - took me some time to find anything that was wrong. Also, the man pages and the provided test file were perfect, you did great with this project version!

[Jsk07211]

Hi all, here's my suggested changes/improvements:

* in scanf, I tested passing strings instead of integers, and they still got converted into integers leading to confusing output. For this, maybe comparing the input strings with the result given by atoi can help. Maybe even simpler logic could work, since I see that you pretty much show length 0, so  you can maybe print something else if your length == 0. In addition, the second part did not seem to work well in most cases:
  `scanf:`
  `Input two integers(space separated, can be negative): a b`
  `0 0 0`
  `Input three strings(space separated): hi hello hi`
  `1 hi (null)`

* Passing NULL to the string functions will break them. I tested passing it in strspn and strcat, both of which broke the code (used my own test cases file). Probably just handling NULL cases at the start of each function would solve this (like
  `if str1 == NULL || str2 == NULL) { handle } `

* `-Testing strncat with null:`
  `Concatenated string: Hello, i�"�& (weird output)`
  `Testing strcspn with null:`
  `Span of characters: 10 (passed null - should not be 10`

* For one more tiny thing, my compiler (for some reason) did not like `strtok_r` being called inside `strtok` before it was defined, so simply swapping the function definitions would do the trick(strtok_r before strtok).

The string functions look great - took me some time to find anything that was wrong. Also, the man pages and the provided test file were perfect, you did great with this project version!

Thanks for the code review! With regards to scanf and the integers, it actually returns zero because we used strcspn, so if it encounters any non-digit character (except if it starts with '-' for negative numbers), in this case the length will be a 0, we atoi 0, hence the result :) The second test case for scanf string uses: initialisedbuf0, uninitialisedbuf, initialisedbuf1. Since the first buffer is initialised, it will save the value, while the uninitialised buffer returns null and stops the code, so the third string doesn't actually get read!

With regards to strspn and strcat and null strings (if I understand your test correctly), they simply seg fault in the standard C String library. For strncat, this could be because it relies on the programmer to correctly input the size of the destination buffer, but thank you for the wonderful suggestion! We will definitely add it to our implementation just in case :)

Will take note of the strtok_r and strtok issue as well! Thank you for the comments!!

[sghahghahi]

You both did a very nice job incorporating useful string functions into xv6. @atanaspatterson made some great observations that I'd like to add to. Here's one vulnerability I found in scanf():

scanf() is easy to break with a buffer overflow. We get a usertrap() if the user input is significantly larger than the buffer size

• A useful addition to scanf() might be a check for a field width specifier like this:

• char buf[100];
  scanf("%99s", buf); // Only read 99 characters

Again, well done with this project and thank you for adding some much-needed (and well-documented) string functions to xv6!

[allureking]

Memory Leak Analysis from Honghuai Ke for this String Library Implementation Project

Leak Check Report

-- Leak Check --
[BLOCK 0x0000000000006140] 160  getline
-- Summary --
160 blocks lost (4096 bytes)

I conducted a thorough memory leak check on the string library implementation, focusing on the getline function, which was identified as a potential source of leaks. Here are the results from my own malloc_leaks() utility: Leak Detected: 160 blocks totaling 4096 bytes Location: Allocations made within the getline function

Findings The leak check revealed that the getline function does not properly free memory that it allocates during execution. This has resulted in a significant memory leak, as evidenced by the memory not being released back to the system.

Suggested Solutions

1. Review and Refactor getline:

• The function should be carefully reviewed to ensure that all allocated memory is freed correctly before the function exits. This may involve adding specific free() calls at points where memory is no longer needed.
• Consider implementing a cleanup section within the function to handle all error paths and ensure memory is always freed.

2. Implement Comprehensive Unit Tests:

• Develop unit tests that specifically check for memory allocation and deallocation within getline.
• Use the malloc_leaks() utility as part of regular testing to catch any future regressions.

[Jsk07211]

One of our test cases for scanf tested for a null buffer, which meant free(copy) didn't run. It has since been fixed :D

[allureking]

One of our test cases for scanf tested for a null buffer, which meant free(copy) didn't run. It has since been fixed :D

I was just about to add to my previous commment that after further investigating, the memory allocated by getline is actually not being properly freed by scanf, which should be responsible for the lifecycle of this memory. Below are the two places of where free should be added:

At line 18: Add free(copy); after the completion of its usage. At line 77: Ensure free(copy); is added to handle all exit points where getline memory might not be freed.

I saw that you've already fixed it, great job!