The AF system sensors are located in the floor of the mirror box. They receive the image through the semi-silvered mirror, which is then reflected downward by a secondary mirror hinged to the back of the main mirror. This forms a virtual focusing plane that is supposed to be at the exact same plane as the sensor (a point of possible miscalibration).
Each AF sensor consists of a pair of short lines of pixels forming an array. One array comprises the outer sensors. Two crossed arrays (one vertical, one horizontal) comprise the center sensor. With lenses or f2.8 or faster, the camera activates a second vertical array in the center.
The arrays are sensitive to linear details that run perpendicular to the orientation of the array. Therefore, the horizontal arrays (identified by the horizontal rectangle marks on the viewscreen) are sensitive to vetical linear details; the vertical arrays (identified by the vertical rectangle marks on the viewscreen) are sensitive to horizontal linear details.
They are blind to linear details that run parallel to the array direction. The center array, being a crossed combination of a vertical and a horizontal array, is sensitive to linear details running both vertically and horizontally. When the second vertical array is activated, it's combined input increases the accuracy by a factor of three.
The pixel arrays are actually three times longer than indicated by the viewfinder markings. This is to cover the fact that the viewscreen has a significant amount of "slop" in its horizontal-plane positioning (what you see as left/right/up/down in the viewfinder). Therefore, the sensors actually see details that are somewhat outside the viewfinder markings, and may focus on them instead of details within the sensor markings, if those outside details are more perpendicular to the array than the details inside the markings.
When you mount a lens (whether the camera is on or off), the camera interrogates the lens for its characteristics, including maximum aperture, which one of the focusing parameters.
When you half-press the shutter release (or the * button, if you've used the custom function to move focusing control there), the activated AF sensor "looks" at the image projected by the lens from two different directions (each line of pixels in the array looks from the opposite direction of the other) and identifies the phase difference of the light from each direction. In one "look," it calculates the distance and direction the lens must be moved to cancel the phase differences. It then commands the lens to move the appropriate distance and direction and stops. It does not "hunt" for a best focus, nor does it take a second look after the lens has moved (it is an "open loop" system).
If the starting point is so far out of focus that the sensor can't identify a phase difference, the camera racks the lens once forward and once backward to find a detectable difference. If it can't find a detectable difference during that motion, it stops.
Although the camera does not take a "second look" to see if the intended focus has been achieved, the lens does take a "second look" to ensure it has moved the direction and distance commanded by the camera (it is a "closed loop" system). This second look corrects for any slippage or backlash in the lens mechanism, and can often be detected as a small "correction" movement at the end of the longer initial movements.
When the camera determines how far and in what direction the lens must move to cancel the phase difference, it does so within a tolerance of "within the depth of focus" of lenses slower than f2.8 (down to f5.6) or "within 1/3 of the depth of focus" of lenses f2.8 and faster. The depth of focus is the range at the sensor plane within which the image of a point will be reproduced as a blur smaller than the manufacturer's designated "circle of confusion" (CoC). Canon's designated circle of confusion is 0.035mm for the 24x36mm format and 0.02mm for the APS-C format. The CoC is based on maintaining the appearance of sharpness in a 6x9 inch print at about an 10 inch viewing distance (as revealed by the Euro-Canon web site). There is no guarantee that images enlarged any greater than this will appear sharp.
The depth of focus increases when the aperture of the lens decreases (like depth of field at the subject plane), but it does not change with the focused distance or the focal length of the lens (according to Canon, unlike depth of field). That is why the camera interrogates the lens for that information; it calculates the depth of focus tolerance from the maximum aperture, not the set working aperture.
As a result of this tolerance (within the depth of focus or within 1/3 of the depth of focus), the camera can place the actual plane of focus at random anywhere within the tolerance range, and not necessarily at the same place each time.