Peeter Joot's (OLD) Blog.

Math, physics, perl, and programming obscurity.

Archive for May, 2012

updated compilation of class notes for phy454h1s, continuum mechanics.

Posted by peeterjoot on May 28, 2012

As mentioned previously I’ve got a compilation of class notes here:

https://sites.google.com/site/peeterjoot2/math2012/phy454.pdf

This has been updated now with many changes that should make it easier to read. These notes are no longer follow the exact order of the lectures, but are grouped by topic, with the various problems incorporated into the chapter content as Problems/Solutions sections. Some stuff is moved to appendixes, and some parts just plain deleted. There are a number of cosmetic changes too, the biggest of which is style overhaul resulting from a switch to the book class to the classicthesis style (not strictly for thesis content since it provides an elegant general book template and framework).

Advertisements

Posted in Math and Physics Learning. | Tagged: , , , , , | Leave a Comment »

latex colors

Posted by peeterjoot on May 16, 2012

I’d seen in wikipedia a list of colors for latex, but some of them didn’t work for me. Looking in the .log file from my latex compilation, I found the path to the color definitions in effect for my document and ran a bit of search and replace to create the following

\documentclass[openany]{memoir}
\usepackage[svgnames]{xcolor}

\begin{document}

\color{AliceBlue}{AliceBlue}
\color{AntiqueWhite}{AntiqueWhite}
\color{Aqua}{Aqua}
\color{Aquamarine}{Aquamarine}
\color{Azure}{Azure}
\color{Beige}{Beige}
\color{Bisque}{Bisque}
\color{Black}{Black}
\color{BlanchedAlmond}{BlanchedAlmond}
\color{Blue}{Blue}
\color{BlueViolet}{BlueViolet}
\color{Brown}{Brown}
\color{BurlyWood}{BurlyWood}
\color{CadetBlue}{CadetBlue}
\color{Chartreuse}{Chartreuse}
\color{Chocolate}{Chocolate}
\color{Coral}{Coral}
\color{CornflowerBlue}{CornflowerBlue}
\color{Cornsilk}{Cornsilk}
\color{Crimson}{Crimson}
\color{Cyan}{Cyan}
\color{DarkBlue}{DarkBlue}
\color{DarkCyan}{DarkCyan}
\color{DarkGoldenrod}{DarkGoldenrod}
\color{DarkGray}{DarkGray}
\color{DarkGreen}{DarkGreen}
\color{DarkGrey}{DarkGrey}
\color{DarkKhaki}{DarkKhaki}
\color{DarkMagenta}{DarkMagenta}
\color{DarkOliveGreen}{DarkOliveGreen}
\color{DarkOrange}{DarkOrange}
\color{DarkOrchid}{DarkOrchid}
\color{DarkRed}{DarkRed}
\color{DarkSalmon}{DarkSalmon}
\color{DarkSeaGreen}{DarkSeaGreen}
\color{DarkSlateBlue}{DarkSlateBlue}
\color{DarkSlateGray}{DarkSlateGray}
\color{DarkSlateGrey}{DarkSlateGrey}
\color{DarkTurquoise}{DarkTurquoise}
\color{DarkViolet}{DarkViolet}
\color{DeepPink}{DeepPink}
\color{DeepSkyBlue}{DeepSkyBlue}
\color{DimGray}{DimGray}
\color{DimGrey}{DimGrey}
\color{DodgerBlue}{DodgerBlue}
\color{FireBrick}{FireBrick}
\color{FloralWhite}{FloralWhite}
\color{ForestGreen}{ForestGreen}
\color{Fuchsia}{Fuchsia}
\color{Gainsboro}{Gainsboro}
\color{GhostWhite}{GhostWhite}
\color{Gold}{Gold}
\color{Goldenrod}{Goldenrod}
\color{Gray}{Gray}
\color{Green}{Green}
\color{GreenYellow}{GreenYellow}
\color{Grey}{Grey}
\color{Honeydew}{Honeydew}
\color{HotPink}{HotPink}
\color{IndianRed}{IndianRed}
\color{Indigo}{Indigo}
\color{Ivory}{Ivory}
\color{Khaki}{Khaki}
\color{Lavender}{Lavender}
\color{LavenderBlush}{LavenderBlush}
\color{LawnGreen}{LawnGreen}
\color{LemonChiffon}{LemonChiffon}
\color{LightBlue}{LightBlue}
\color{LightCoral}{LightCoral}
\color{LightCyan}{LightCyan}
\color{LightGoldenrod}{LightGoldenrod}
\color{LightGoldenrodYellow}{LightGoldenrodYellow}
\color{LightGray}{LightGray}
\color{LightGreen}{LightGreen}
\color{LightGrey}{LightGrey}
\color{LightPink}{LightPink}
\color{LightSalmon}{LightSalmon}
\color{LightSeaGreen}{LightSeaGreen}
\color{LightSkyBlue}{LightSkyBlue}
\color{LightSlateBlue}{LightSlateBlue}
\color{LightSlateGray}{LightSlateGray}
\color{LightSlateGrey}{LightSlateGrey}
\color{LightSteelBlue}{LightSteelBlue}
\color{LightYellow}{LightYellow}
\color{Lime}{Lime}
\color{LimeGreen}{LimeGreen}
\color{Linen}{Linen}
\color{Magenta}{Magenta}
\color{Maroon}{Maroon}
\color{MediumAquamarine}{MediumAquamarine}
\color{MediumBlue}{MediumBlue}
\color{MediumOrchid}{MediumOrchid}
\color{MediumPurple}{MediumPurple}
\color{MediumSeaGreen}{MediumSeaGreen}
\color{MediumSlateBlue}{MediumSlateBlue}
\color{MediumSpringGreen}{MediumSpringGreen}
\color{MediumTurquoise}{MediumTurquoise}
\color{MediumVioletRed}{MediumVioletRed}
\color{MidnightBlue}{MidnightBlue}
\color{MintCream}{MintCream}
\color{MistyRose}{MistyRose}
\color{Moccasin}{Moccasin}
\color{NavajoWhite}{NavajoWhite}
\color{Navy}{Navy}
\color{NavyBlue}{NavyBlue}
\color{OldLace}{OldLace}
\color{Olive}{Olive}
\color{OliveDrab}{OliveDrab}
\color{Orange}{Orange}
\color{OrangeRed}{OrangeRed}
\color{Orchid}{Orchid}
\color{PaleGoldenrod}{PaleGoldenrod}
\color{PaleGreen}{PaleGreen}
\color{PaleTurquoise}{PaleTurquoise}
\color{PaleVioletRed}{PaleVioletRed}
\color{PapayaWhip}{PapayaWhip}
\color{PeachPuff}{PeachPuff}
\color{Peru}{Peru}
\color{Pink}{Pink}
\color{Plum}{Plum}
\color{PowderBlue}{PowderBlue}
\color{Purple}{Purple}
\color{Red}{Red}
\color{RosyBrown}{RosyBrown}
\color{RoyalBlue}{RoyalBlue}
\color{SaddleBrown}{SaddleBrown}
\color{Salmon}{Salmon}
\color{SandyBrown}{SandyBrown}
\color{SeaGreen}{SeaGreen}
\color{Seashell}{Seashell}
\color{Sienna}{Sienna}
\color{Silver}{Silver}
\color{SkyBlue}{SkyBlue}
\color{SlateBlue}{SlateBlue}
\color{SlateGray}{SlateGray}
\color{SlateGrey}{SlateGrey}
\color{Snow}{Snow}
\color{SpringGreen}{SpringGreen}
\color{SteelBlue}{SteelBlue}
\color{Tan}{Tan}
\color{Teal}{Teal}
\color{Thistle}{Thistle}
\color{Tomato}{Tomato}
\color{Turquoise}{Turquoise}
\color{Violet}{Violet}
\color{VioletRed}{VioletRed}
\color{Wheat}{Wheat}
\color{White}{White}
\color{WhiteSmoke}{WhiteSmoke}
\color{Yellow}{Yellow}
\color{YellowGreen}{YellowGreen}

\end{document}

This produces the following

xcolor svgnames

Posted in Math and Physics Learning. | Tagged: , | Leave a Comment »

Fun with platform linker inconsistencies (AIX vs. Linux)

Posted by peeterjoot on May 10, 2012

Imagine we have three source files, to be built into a pair of shared libs (one with a dependency on the other) and an exe as in:

// s1.C
extern "C" void foo(void){}

// s2.C
extern "C" void foo(void) ;
extern "C" void bar(void){foo();}

// m.C
extern "C" void foo(void) ;
extern "C" void bar(void) ;

int main()
{
   bar() ;
   foo() ;
   return 0 ;
}

On Linux, we can compile and link these with command line of the following sort

# g++ -shared s1.C -o libs1.so -fpic
# g++ -shared s2.C -o libs2.so -fpic -L. -ls1
# g++ -L. -ls2 m.C -Wl,-rpath-link,`pwd` -Wl,-rpath,`pwd`

Notice that we’ve not explicitly linked to libs1.so on Linux, even though we are using a symbol from it explictly. The linker picks up dependencies from other things that you choose to link to.

On AIX the equivalent commands to create a pair of shared libraries and link the exe to it fails at that exe link

# xlC -q64 -qmkshrobj s1.C -o shr1.o
# ar -X64 -crv libs1.a shr1.o
# xlC -q64 -qmkshrobj s2.C -o shr2.o -L. -ls1
# ar -X64 -crv libs2.a shr2.o
# xlC -q64 -L. -ls2 m.C
ld: 0711-317 ERROR: Undefined symbol: .foo
ld: 0711-345 Use the -bloadmap or -bnoquiet option to obtain more information.

You’ve got to add -ls1 to those link flags to get the exe to find its dependencies. I wonder which of these two link time behaviours is more common?

Posted in C/C++ development and debugging. | Tagged: , , , , | Leave a Comment »

A common anti-pattern: mutex acquire is freeable.

Posted by peeterjoot on May 7, 2012

Again and again in DB2 code, developers appear to have discovered a “clever” way to manage shared memory cleanup of memory that is protected by a mutex (what is called a latch internally in the DB2 codebase). The pattern is roughly of the following form:

struct myStuff
{
   mutex m ;
   // ... other stuff.
} ;

void myStuffCleanup( myStuff * pSharedMem )
{
   if ( pSharedMem->m.acquire() )
   {
      freeMemory( pSharedMem ) ;
   }
}

The developer coding this, based on other state and knowledge of when the myStuffCleanup function is executed, knows that if they get to this point in the code, no new attempts to acquire the mutex will ever be made. However, before the memory can be freed, there needs to be some sort of guarentee that all the old users of the memory (and mutex) are gone.

For cleanup problems like this we appear to have a number of developers that have been clever enough to realize that the last thing any consumer of this memory will ever do is release the mutex. So, they code an acquire guard like the above, believing that if the mutex can be acquired at this point in the code, they can “safely” free the memory. However, it is actually unfortunately that the developer has been clever enough to figure out this easy way to handle the cleanup, because it is not safe.

First off, observe that unless the developer knows the internals of the mutex implementation, this isn’t a terribly safe thing to do. For example, the mutex could internally use something like a Unix semaphore or a Windows EVENT, so cleanup code may be required before the memory containing the mutex is freed.

However, in this case, the mutex implementation in question historically has never required any sort of cleanup (provided it wasn’t in use at the cleanup point). As it happens, we didn’t even historically have a cleanup method for this particular mutex implementation. We have one now, defined for consistency with some of our other mutex implementations which do require explicit cleanup, but it states that it is just for consistency and is a no-op. Reading that documentation (or bad assumptions) is probably what leads the developers to believe that they can free memory containing this mutex type even if it is held.

[An aside.  Our mutex implementation Windows actually does use an EVENT to manage the wait for the myStuffCleanup() acquire caller, and that EVENT HANDLE will still be allocated, assigned to the mutex even after the mutex release.  Our clever developer has gotten lucky because we happen to clean up that EVENT HANDLE in the acquire() call (presuming there really was no other use of the mutex).]

Despite having nothing to cleanup after this last man out acquire, this sort of pattern is neither correct nor safe. What the developer doesn’t know is what our release method does internally. It happens that the operation that logically releases the mutex, allowing it to be acquired, isn’t necessarily the last operation or access of the mutex memory performed by our release code.

Our release code has roughly the following form:

void mutex::release()
{
   validate() ;

   markMutexFree() ;

   wakeupAnyWaitersIfAppropriate() ;

   waitlistOperationsIfAny() ; // some platforms only.

   releaseInternalMutexForWaiterManagement() ; // some platforms only.

   logMutexStateToTraceBufferIfTraceIsOn() ;

   validate() ;
}

After that markMutexFree() point in the code, there are a number of possible accesses to the mutex memory. If that “final” release() caller gets context switched out just after that point, and the memory freed before it resumes (or the SMP system is fast enough to allow the free to proceed concurrently while the mutex::release() code executes), then we will be in trouble when the release() code resumes.

Here’s an enumeration of the memory accesses to the mutex after the internal-“release” that makes it available for new acquire:

  1. waitlistOperationsIfAny().  On our Unix platforms for this mutex type we keep what we call a waitlist, one for all the write (exclusive) waiters, and one for all the read (shared) waiters for the mutex.  Similarily in our Windows mutex implementation we have an EVENT HANDLE pointer in the mutex (although we don’t update that in release after the wakeup like we do on Unix).  After we’ve released the mutex, we’ll wake up any waiters, and then store the new waitlist values in the mutex.  In this scenerio we’ll be storing only a zero as the new waitlist value, because there’s either no waiters, or the only waiter should be the cleanup caller, and we’ll have just woken up that “last waiter”.  We happen to avoid a requirement for actually storing the waitlist separately for our 64-bit Unix implementation, but we do still unfortunately ship a 32-bit server version of DB2 (a developer only version that runs on Linux ia32).  Long story made short, if the memory is recycled after acquire and that happens before these waitlist stores, these zero stores could be corrupting memory (or attempting to access memory that could be unmapped).
  2. releaseInternalMutexForWaiterManagement().  Our Windows and 32-bit Unix implementations currently have an internal mutex (in this case, a plain old spinlock, not a reader/writer mutex) that we use for storing either our waitlist pointer or an pointer to our EVENT handles for the mutex.  This internal mutex free will result in a store (i.e a store zero), plus some memory barrier instructions if appropriate.  Again, if the mutex memory has been free()’d, this would be bad.
  3. logMutexStateToTraceBufferIfTraceIsOn().  This is problem determination and performance related tracing.  It may or may not be enabled at runtime, but should be alllowed to look at the mutex state if executed.  If the memory has been free()’d and unmapped then this trace code would look at the mutex memory, and could trap.
  4. Our final validate() call.  This regularly finds code that uses this free-if-I-can-acquire pattern, since our mutex is fairly stateful, and good for catching this pattern.  In particular, the memset to 0xDD that occurs in our free() code will set inappropriate bits that validate() complains about.

There have been developers that have objected to our final validate() call, saying that we shouldn’t be doing it (or any other operation on the mutex) after the logical release point.   They’d like this to be our bug, not theirs.  To win this working-as-designed argument, we essentially have to argue that what has been done is free memory that has been passed to a function that is still operating on it.

I’d be curious to know if this pattern of acquire mutex and then destroy memory containing it is common in other codebases (using other mutex types).  If this is a common pattern, I wonder how many other types of mutex implementations can tolerate a free of the mutex memory while the release code for an uncontended mutex is still executing?  Our pure spinlock implementation happens to be able to tolerate this, and does no further access to the mutex memory after the logical release.  However, our reader-writer mutex (the mutex type in question here), cannot tolerate this sort of free while in use on some platforms … but we abort unconditionally if detected on any.

Posted in C/C++ development and debugging. | Tagged: , , , , , | Leave a Comment »

A Fourier series refresher.

Posted by peeterjoot on May 3, 2012

[Click here for a PDF of this post with nicer formatting]

Motivation.

I’d used the wrong scaling in a Fourier series over a [0, 1] interval. Here’s a reminder to self what the right way to do this is.

Guts

Suppose we have a function that is defined in terms of a trigonometric Fourier sum

\begin{aligned}\phi(x) = \sum c_k e^{i \omega k x},\end{aligned} \hspace{\stretch{1}}(2.1)

where the domain of interest is x \in [a, b]. Stating the problem this way avoids any issue of existence. We know c_k exists, but just want to find what they are given some other representation of the function.

Multiplying and integrating over our domain we have

\begin{aligned}\begin{aligned}\int_a^b \phi(x) e^{-i \omega m x} dx &= \sum c_k \int_a^b e^{i \omega (k -m) x} dx \\ &= c_m (b - a) + \sum_{k \ne m} \frac{e^{i \omega(k-m) b} - e^{i \omega(k-m)a}}{i \omega (k -m)} .\end{aligned}\end{aligned} \hspace{\stretch{1}}(2.2)

We want all the terms in the sum to be be zero, requiring equality of the exponentials, or

\begin{aligned}e^{i \omega (k -m) (b -a )} = 1,\end{aligned} \hspace{\stretch{1}}(2.3)

or

\begin{aligned}\omega = \frac{2 \pi}{b - a}.\end{aligned} \hspace{\stretch{1}}(2.4)

This fixes our Fourier coefficients

\begin{aligned}c_m = \frac{1}{{b - a}} \int_a^b \phi(x) e^{- 2 \pi i m x/(b - a)} dx.\end{aligned} \hspace{\stretch{1}}(2.5)

Given this, the correct (but unnormalized) Fourier basis for a [0, 1] interval would be the functions e^{2 \pi i x}, or the sine and cosine equivalents.

References

Posted in Math and Physics Learning. | Tagged: , | Leave a Comment »