user
274 lines
9.4 KiB
TeX
274 lines
9.4 KiB
TeX
\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<T>}.
|
|
|
|
\end{document}
|