Report

[iledesma08]

Summary

This issue will describe the making of this project and answer some given questions

[iledesma08]

Project Planning Phase Summary

First, I had to recognize the milestones for this project. Based on the README.md provided, the project involves advanced memory management and file system exploration. I have divided this project into the next key stages and milestones to follow:

1. Initial Setup and Baseline Code Assessment

   • Familiarize with the provided memory management library, existing functions, and structure.
   • Conduct initial tests to identify the limitations of current memory allocation and deallocation processes.

2. Milestone 1: Optimization of Memory Allocation

   • Block Fusion and Compaction: Implement modifications in the fusion function to automatically compact free memory blocks during free operations, reducing fragmentation.
   • Heap Consistency Check: Extend check_heap() to detect heap inconsistencies like unmerged free blocks or invalidly sized allocated blocks.
   • Memory Analysis and Reporting: Add a function memory_usage() to report allocated block sizes and available free memory.
   • Event Logging: Introduce detailed logging for operations such as malloc, calloc, free, and realloc to allow in-depth memory use audits.

3. Milestone 2: Enhanced Memory Allocation Policies

   • Policy Selection Enhancement: Implement an allocation strategy using the Worst Fit policy. Extend find_block() to locate the largest block for allocation, supporting the setting set_method(2).
   • Policy Efficiency Testing: Develop a test to evaluate efficiency for First Fit, Best Fit, and Worst Fit policies, measuring fragmentation levels and allocation speed.

4. Milestone 3: File System Exploration

   • Directory and Configuration File Search: Add a command in the shell to list configuration files in a specified directory, and allow recursive searching for .config or .json files.
   • File Reading and Data Extraction: Create functionality to extract data from configuration files, simulating a critical system configuration loading process.

5. Milestone 4: Memory Usage Monitoring and Grafana Integration

   • Advanced Metrics and Fragmentation Reporting: Calculate and expose memory fragmentation rates and policy usage statistics (e.g., frequency of each allocation policy).
   • Grafana Visualization: Configure Grafana to display memory usage metrics, allowing visualization of the impact of memory management optimizations.

6. Testing and Quality Assurance

   • Code Coverage Goal: Aim for at least 5% test coverage to ensure essential functionality is verified.
   • Pipeline Integration: Set up GitHub Actions for continuous integration, including cppcheck for code analysis and quality control.

7. Project Completion and Documentation

   • Complete and document all development steps, including explanations for implemented allocation policies and optimizations.
   • Ensure that all project questions in the README.md are addressed, covering memory policy comparisons, compacting benefits, and debugging tools used.

Each milestone is aimed at incrementally improving the project’s efficiency, functionality, and reliability, with a final emphasis on testing, monitoring, and documentation to ensure system robustness.

[iledesma08]

Analysis of memory.h and memory.c files

These files reveal the following structures and functions that are central to the memory management project:

• memory.h:
  • Defines core structures for memory blocks, including s_block, which manages metadata like size, pointers to adjacent blocks, and free status.
  • Declares functions essential for block management, such as find_block(), fusion(), extend_heap(), and allocation functions malloc(), calloc(), realloc(), and free()
• memory.c:
  • Implements memory allocation functions that provide detailed control over block management, including alignment, block fusion, and memory expansion with mmap.
  • Incorporates allocation strategies like First Fit and Best Fit, and code structure for potentially adding Worst Fit.
  • Additional functions handle memory copy (copy_block()), heap consistency check (check_heap()), and adaptive allocation strategies (malloc_control()) .

[iledesma08]

Milestones 1 and 2

Heap Check, Memory Usage and Efficiency Tests

More Runs of Efficiency Test

Conclusions

From the results shown, several conclusions can be drawn regarding the efficiency and fragmentation behavior for each allocation method:

Fragmentation Analysis:

1. First Fit:

   • Consistently shows high external fragmentation (>95%).
   • The method prioritizes finding the first block that fits, which tends to leave small free blocks scattered across the memory, reducing the size of the largest free block.

2. Best Fit:

   • Shows significantly lower external fragmentation (typically around 30%-40%) compared to First Fit.
   • Best Fit tries to find the smallest suitable block, which leads to better utilization of memory but might leave very small free spaces that can no longer be used, increasing fragmentation slightly.

3. Worst Fit:

   • Shows either zero or minimal fragmentation in most cases.
   • Allocating the largest block minimizes leftover free spaces, making this method effective in reducing external fragmentation. However, it can lead to inefficient use of memory over time since large free blocks are consumed first.

Efficiency (Allocation and Deallocation Times):

1. First Fit:

   • Fastest allocation times, consistently lower than Best Fit and Worst Fit.
   • This is expected since it stops searching as soon as it finds the first block that fits.

2. Best Fit:

   • Slower than First Fit due to the additional overhead of searching for the smallest suitable block.
   • Deallocation times are roughly equal across all methods.

3. Worst Fit:

   • Slowest allocation times, significantly higher than both First Fit and Best Fit.
   • The overhead of finding the largest block contributes to the increased time complexity.

Observations and Potential Improvements:

1. First Fit:

   • While it is the fastest allocation method, the very high external fragmentation makes it less suitable for applications requiring efficient memory usage.

2. Best Fit:

   • Strikes a balance between fragmentation and allocation time, making it a good choice for general-purpose scenarios.

3. Worst Fit:

   • Minimal fragmentation makes it appealing for cases where memory utilization is critical, but the slow allocation times make it less efficient for high-frequency memory operations.

Recommendations:

1. For an application that prioritizes speed over memory utilization, First Fit is the best choice.
2. For an application that requires a balance between memory efficiency and allocation time, Best Fit is the optimal choice.
3. For an application that involves scenarios where fragmentation must be minimized, consider Worst Fit, but be aware of the trade-off in allocation speed.

The specific use case will determine the best strategy to use. For instance:

• Real-time systems may favor First Fit for its speed.
• Applications with constrained memory environments may favor Best Fit or Worst Fit depending on memory access patterns.

[iledesma08]

Valgrind and Heaptrack use

The tests above work with both Valgrind error detector and Heaptrack, but in order not to show the same thing again and condense the amount of images, only the images of Valgrind and Heaptrack being used for the efficiency test are shared (this test is far more complex than memory_usage() and check_heap()).

Note: Debug vs Release Profile

For both of these tests, Release profile had to be use when compiling this project. When using the debug profile, more memory is used that has nothing to do with the program itself.

When you use the debug profile instead of the release profile, your program typically consumes more memory for several reasons:

1. Debugging Information

• Debug Symbols: The debug profile includes additional metadata for debugging purposes (e.g., variable names, types, file locations, line numbers). This data is stored alongside the program in memory and on disk, increasing memory usage.
• Instrumentation: Debug builds often include instrumentation code that helps tools like gdb or Valgrind to trace execution flow and monitor program states. This code requires additional memory.

2. Lack of Optimization

• No Compiler Optimizations:
  • The debug profile usually disables compiler optimizations for ease of debugging. This means the code isn’t streamlined, leading to:
    • Larger executable sizes.
    • Less efficient memory usage (e.g., unoptimized stack and heap allocations).
• Inlining and Dead Code:
  • In release mode, functions may be inlined or unused code removed, reducing memory overhead. In debug mode, these optimizations are typically disabled.

3. Increased Runtime Metadata

• Assertions and Error Checks: Debug builds may include additional runtime checks like boundary checks, assertions, or logging, which can consume more memory.
• Memory Allocator Overheads: Some debuggers use custom memory allocators in debug mode, which add metadata to track allocations and deallocations, increasing memory usage.

4. Larger Data Structures

• Padding and Alignment: To make debugging easier, structures may include padding or forced alignment, leading to larger-than-necessary memory footprints.
• Unoptimized Variable Lifetimes: Debug builds often keep variables in memory longer to allow inspection, even if they could have been deallocated in optimized release builds.

5. Debugging Libraries

• Debug builds link against debugging versions of libraries (e.g., libc or libstdc++ in debug mode), which may include additional memory usage for internal tracking, logging, or debugging symbols.

The additional memory usage in debug mode is due to the trade-off between debug visibility and performance. While this is expected, careful configuration of debug settings can minimize the memory overhead while retaining essential debugging features.

Valgrind error detector

Debug profile:

Release profile:

Here you can notice the difference in memory usage and allocations if using the Debug profile or the Release profile

Valgrind Conclusions:

Valgrind is a powerful tool for detecting memory management issues in programs. Its primary purposes are:

1. Memory Leak Detection: Identifies blocks of memory that are allocated but never freed, which can lead to memory leaks.
2. Invalid Memory Access: Detects attempts to read/write to memory that hasn’t been properly allocated or has already been freed.
3. Memory Corruption: Identifies overflows and underflows where memory is accessed outside the bounds of an allocated block.
4. Uninitialized Memory Usage: Detects when uninitialized memory is read, which can lead to unpredictable program behavior.
5. Profiling: Provides detailed information about memory usage, allocations, and deallocations for performance analysis.

From Valgrind Output:

1. Memory Summary:

   • In-use at exit: 0 bytes in 0 blocks.
     • This indicates that all memory allocated during the program's execution has been successfully freed. There are no memory leaks.
   • Total heap usage: 1 allocs, 1 frees, 1024 bytes allocated.
     • A total of 1 allocations and corresponding deallocations occurred, with 1024 bytes of memory allocated during the program's runtime (it looks like it doesnt detect allocations and frees implemented by myself).

2. Leak Check:

   • All heap blocks were freed: Indicates no memory leaks occurred, meaning your program properly manages allocated memory.

3. Error Summary:

   • 0 errors from 0 contexts: Confirms that no invalid memory accesses, uninitialized reads, or similar issues were detected.

Heaptrack

The output from Heaptrack provides valuable insights into program's memory allocation behavior. Here's what the data tells:

1. Summary:

   • Total runtime: program took 0.252s to execute.
   • Peak Heap Memory Consumption: 74.8 KB.
   • Peak RSS (Resident Set Size): 37.1 MB (includes Heaptrack overhead).
   • Total Memory Leaked: 1 KB (small but worth investigating).

2. Memory Allocations:

   • Calls to allocation functions: 2 (very low, suggesting minimal dynamic memory usage).
   • Temporary allocations: 0, indicating that memory was reused effectively during runtime.
   • The memory is likely statically allocated or minimal dynamic allocations occurred.

3. Peak Contributions:

   • 73.7 KB peak memory was consumed from an unresolved function.
   • 1 KB came from the _IO_file_doallocate function in the C library, indicating a standard file I/O allocation.

4. Largest Memory Leak:

   • 1 KB from _IO_file_doallocate. This suggests that some file-handling operation (fopen, fread, or fwrite) did not properly release resources, possibly due to a missing fclose.

Graphs

1. Memory Consumption Over Time:

   • The green section represents unresolved allocations.
   • Memory usage remains consistent, peaking at 74.8 KB.
   • Indicates a stable memory profile, as memory consumption doesn't grow unexpectedly over time.

2. Total Allocations Graph:

   • The blue and green sections align with total memory allocations and unresolved allocations.
   • The flat shape of the graph confirms there are no significant spikes or drops in allocations, implying predictable memory behavior.

Conclusions About the Program

• Efficient Memory Usage: The program maintains a small memory footprint (74.8 KB peak heap consumption). This is excellent for resource-constrained systems.
• No Major Leaks: Only 1 KB of leaked memory is detected, which is minimal. However, it still indicates a potential issue with file I/O that should be addressed.
• File Handling Issues: The memory leak in _IO_file_doallocate suggests a missing or improperly handled fclose or related cleanup operation.
• Predictable Behavior: The program does not show signs of excessive memory fragmentation or unpredictable allocation patterns.

Taken Actions

Couldnt address the memory leak. It must be related to the use of heaptrack or a used library.

[iledesma08]

Milestone 3

Implemented recursive file search succesfully. Let's see some examples of use:

.config files

.txt files

.json files

No directory or filetype provided

Wrong directory or filetype provided