\documentclass[10pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage[polish]{babel} \usepackage[a4paper,margin=1.55cm]{geometry} \usepackage{array,tabularx,booktabs} \usepackage{amsmath,amssymb} \usepackage{xcolor,listings} \usepackage{hyperref,fancyhdr,lastpage,enumitem} \definecolor{accent}{HTML}{16324A} \definecolor{accentlight}{HTML}{EEF3F7} \definecolor{rulegray}{HTML}{D7DEE5} \hypersetup{colorlinks=true,linkcolor=accent,urlcolor=blue} \IfFileExists{build-meta.tex}{\input{build-meta.tex}}{\newcommand{\BuildCommit}{local}} \newcommand{\PublisherDomain}{mpabi} \newcommand{\CardArea}{inf} \newcommand{\CardSeries}{freertos-cpp} \newcommand{\CardNumber}{05} \newcommand{\CardCount}{16} \newcommand{\CardSlug}{heap-models} \newcommand{\CardVersion}{v00.01} \newcommand{\DocumentUUID}{c456b505-dc5c-4894-b832-bb4c5afd0feb} \newcommand{\blank}[1]{\rule{#1}{.2pt}} \lstset{ language=C++,basicstyle=\ttfamily\scriptsize,columns=fullflexible, keepspaces=true,frame=single,breaklines=true,showstringspaces=false, numbers=none,backgroundcolor=\color{accentlight},rulecolor=\color{rulegray} } \pagestyle{fancy} \fancyhf{} \lhead{\textbf{K05 · FreeRTOS C++ · heap}} \rhead{\small L04 · modele, most i statystyki} \lfoot{\scriptsize commit \BuildCommit} \cfoot{\scriptsize \thepage/\pageref{LastPage}} \rfoot{\scriptsize V11.3.0 / \CardVersion} \setlength{\headheight}{14pt} \setlength{\footskip}{19pt} \setlist[itemize]{nosep,leftmargin=1.45em} \setlist[enumerate]{nosep,leftmargin=1.65em} \begin{document} \sloppy \begin{center} {\LARGE\bfseries Most C++ do heapu, modele i \texttt{HeapStats}}\par \vspace{.25em} {\large suma wolnych bajtów nie jest największym blokiem}\par \end{center} \noindent\begin{tabularx}{\textwidth}{@{}p{1.65cm}Xp{1.55cm}X@{}} \toprule Karta & K05 / \CardCount & Czas & 30 minut \\ Platforma & Hazard3 / RV32I & Język & freestanding C++17 \\ Allocator & prawdziwy \texttt{heap\_4.c} & Kernel & V11.3.0, bez zmian \\ Wersja & \CardVersion & UUID karty & \texttt{c456b505-...} \\ \bottomrule \end{tabularx} \section*{Trzy pytania, jeden eksperyment} \begin{enumerate} \item Która polityka \texttt{heap\_1...heap\_5} pasuje do topologii pamięci? \item Czy każdy wariant \texttt{new/delete} trafia do jednego heapu FreeRTOS? \item Czy bieżące free, największy blok i minimum-ever dowodzą tego samego? \end{enumerate} \noindent\fcolorbox{accent}{accentlight}{% \begin{minipage}{.94\textwidth} \textbf{Inwariant K05.} Każdy żywy blok ma właściciela, a każda decyzja o pojemności używa co najmniej pary: suma wolnych bajtów i największy wolny blok. Minimum-ever jest historią i nie rośnie po zwolnieniu pamięci. \end{minipage}} \section*{Plan 30 minut} \noindent\begin{tabularx}{\textwidth}{@{}p{1.35cm}p{3.0cm}X@{}} \toprule Czas & Tryb & Dowód ucznia \\ \midrule 0--5 & wybór modelu & heap dla trzech scenariuszy \\ 5--9 & most C++ & komplet scalar/array, sized/unsized \\ 9--14 & predykcja & układ A--B--C i dwie dziury po free \\ 14--21 & fragmentacja & largest $<$ request $<$ total, wynik NULL \\ 21--26 & koalescencja & jedno free, identyczny request działa \\ 26--30 & historia & current wraca, minimum-ever zostaje \\ \bottomrule \end{tabularx} \section*{Najpierw wybierz} Tylko startup, brak free: \blank{2cm}\quad Jedna arena + delete: \blank{2cm}\quad Dwa rozłączne banki RAM: \blank{2cm} \newpage \section{Pięć modeli, ale jeden w obrazie programu} \noindent\begin{tabularx}{\textwidth}{@{}p{1.55cm}p{1.55cm}p{2.2cm}X@{}} \toprule Model & Free & Koalescencja & Kontrakt / typowe użycie \\ \midrule \texttt{heap\_1} & nie & nie dotyczy & monotoniczna arena; alokuj raz i nie zwalniaj \\ \texttt{heap\_2} & tak & nie & odzyskuje bloki, lecz sąsiednie dziury pozostają osobne \\ \texttt{heap\_3} & libc & zależy od libc & deleguje do \texttt{malloc/free}; wymaga heapu linkera \\ \texttt{heap\_4} & tak & sąsiednich & jedna arena FreeRTOS; wybór tej serii na Hazard3 \\ \texttt{heap\_5} & tak & w regionach & wiele regionów zdefiniowanych przed pierwszą alokacją \\ \bottomrule \end{tabularx} \textbf{Nie łączymy implementacji.} Do obrazu linkujemy jeden plik, który definiuje \texttt{pvPortMalloc} i \texttt{vPortFree}. Most C++ zmienia składnię, nie politykę wybranego allocatora. \subsection*{Uzasadnij trzy wdrożenia} \begin{enumerate} \item Wszystkie obiekty powstają przed schedulerem i nigdy nie są usuwane: model \blank{2cm}, ponieważ \blank{9cm}. \item Zadania i kolejki powstają/nikną w jednej arenie RAM: model \blank{2cm}, ponieważ \blank{9cm}. \item Dwa rozłączne banki RAM mają zasilać jeden allocator: model \blank{2cm}, ponieważ \blank{9cm}. \end{enumerate} \section{Kompletny most C++} \begin{lstlisting} void* operator new(size_t n); void* operator new[](size_t n); void operator delete(void* p) noexcept; void operator delete[](void* p) noexcept; void operator delete(void* p, size_t) noexcept; void operator delete[](void* p, size_t) noexcept; \end{lstlisting} \begin{center} \texttt{new/new[] -> pvPortMalloc}\qquad \texttt{delete/delete[] -> vPortFree} \end{center} W profilu bez wyjątków zwykłe \texttt{new} jest \textbf{fail-fast}. Próba kontrolowanej porażki używa jawnie \texttt{pvPortMalloc} i sprawdza \texttt{nullptr}; nie zmienia kontraktu ordinary new. \subsection*{Dlaczego sized delete też musi istnieć?} Kompilator może wybrać wariant z drugim argumentem rozmiaru. Brak definicji oznacza niekompletny most albo zależność od niedostępnego runtime. W ELF zaznacz sześć znalezionych symboli: \blank{10cm} \newpage \section{Eksperyment: total wystarcza, blok nie} \begin{center} \texttt{baseline: [ FREE ......................................... ]}\\[.4em] \texttt{allocate: [ A 2K ][ B 4K ][ C 2K ][ FREE ............... ]}\\[.4em] \texttt{free A,C: [ FREE ][ B LIVE ][ FREE + trailing free ...... ]} \end{center} Po zwolnieniu A i C blok B nadal rozdziela wolne obszary. \texttt{heap\_4} scala C z końcowym free, ale nie może scalić przez żywy B. \noindent\begin{tabularx}{\textwidth}{@{}p{4.9cm}p{3.2cm}X@{}} \toprule Wielkość & Predykcja & Odczyt Hazard3 \\ \midrule \texttt{available\_bytes} & \blank{2.6cm} & \blank{4cm} \\ \texttt{largest\_free\_block} & \blank{2.6cm} & \blank{4cm} \\ \texttt{free\_blocks} & \blank{2.6cm} & \blank{4cm} \\ \texttt{request = largest + 1} & \blank{2.6cm} & \blank{4cm} \\ wynik pierwszej próby & \blank{2.6cm} & \blank{4cm} \\ \bottomrule \end{tabularx} \section*{Relacja, nie przypadkowe liczby} \begin{center} \fbox{\texttt{largest < request < available} \quad i mimo tego \quad \texttt{result == nullptr}} \end{center} Wyjaśnienie: \blank{14cm}\\[1.1em] \blank{16cm} \section*{Zwolnij B i ponów identyczne żądanie} \begin{center} \texttt{free B: [ ONE COALESCED FREE BLOCK ...................... ]} \end{center} Wtedy wymagamy: \begin{itemize} \item \texttt{free\_blocks ==} \blank{1.5cm}; \item \texttt{largest == available == baseline}: \blank{5cm}; \item ponowienie \emph{tego samego} request: \blank{4cm}; \item adres retry leży w \texttt{ucHeap}: \blank{4cm}. \end{itemize} \section*{Nagłówek i wyrównanie też kosztują} Statystyka największego wolnego bloku opisuje blok allocatora. Żądany payload potrzebuje jeszcze wyrównanego nagłówka. Dlatego nie zamieniaj pola \texttt{largest} w bezwarunkową gwarancję payloadu tej samej wielkości. \newpage \section{Siedem checkpointów i historia minimum-ever} \begin{lstlisting}[language=bash] make check riscv64-unknown-elf-gdb build/task01_heap_models/prog.elf b heap_models_debug_checkpoint \end{lstlisting} \noindent\begin{tabularx}{\textwidth}{@{}p{1.05cm}p{3.75cm}X@{}} \toprule STOP & Stan & Obowiązkowy dowód \\ \midrule 1 & baseline & jedno free; zapisz current i minimum-ever \\ 2 & A+B+C żywe & trzy adresy; free spada; payload zachowany \\ 3 & A/C zwolnione & dwa free; total $>$ largest \\ 4 & kontrolowany fail & request między largest i total; alloc count bez zmiany \\ 5 & B zwolnione & jeden blok; largest=current=baseline \\ 6 & retry żywe & ten sam request działa; min-ever osiąga nowe minimum \\ 7 & retry zwolnione & current=baseline, minimum-ever nadal niższe \\ \bottomrule \end{tabularx} \subsection*{Minimalny zestaw GDB} \begin{lstlisting} p g_baseline_stats p g_after_alloc_stats p g_fragmented_stats p g_after_failure_stats p g_coalesced_stats p g_after_retry_stats p g_final_stats p g_cpp_allocation_addresses p g_cpp_deallocation_addresses p g_peak_bytes_used p g_heap_models_pass \end{lstlisting} \section*{Current kontra watermark} \begin{tabularx}{\textwidth}{@{}p{5.4cm}X@{}} \toprule Warunek końcowy & Odczyt \\ \midrule \texttt{final.available == baseline.available} & \blank{6cm} \\ \texttt{final.minimum\_ever < final.available} & \blank{6cm} \\ \texttt{peak = baseline - minimum\_ever} & \blank{6cm} \\ \texttt{alloc/free/live == 3/3/0} dla C++ & \blank{6cm} \\ kolejność zwolnień adresów = A,C,B & \blank{6cm} \\ \texttt{pass == 1} & \blank{6cm} \\ \bottomrule \end{tabularx} \section*{Wyjście} \begin{enumerate} \item Dlaczego 12 KB total free nie obiecuje jednego bloku 10 KB?\\[.8em] \item Co zmieniło zwolnienie B, skoro suma free też tylko wzrosła?\\[.8em] \item Dlaczego minimum-ever nie wróciło wraz z current free?\\[.8em] \item Dlaczego \texttt{heap\_3} nie jest samowystarczalnym wyborem freestanding?\\[.8em] \end{enumerate} \vfill \noindent\textbf{Następna karta K06:} nie-wirtualny \texttt{MemoryResource}, \texttt{HeapResource}, arena statyczna i typowany \texttt{FreeRtosAllocator}. \end{document}